「排序算法」专题 5：「分治思想」经典例子

「排序算法」专题 5：「分治思想」经典例子

这里给出的例题的解题思路如果对于初学者来说可能不是很容易想到，不过其实你只要熟悉归并排序，按照归并排序的套路，是不难写出下面的代码。反正不过我是写不出的，不过我会看别人写的代码，理解之后，自己写出来。如果觉得理解这些代码比较吃力的话，可以暂时跳过，我写出来还是费了很大力气，并且也是调试和一段时间才把代码写正确的。

本节介绍了 3 道例题，它们分别是：计算数组的逆序对、计算右侧小于当前元素的个数、最大子序和。

例1：《剑指 Offer》（第 2 版）第 51 题：计算数组的逆序对

• 链接：《剑指 Offer》（第 2 版）第 51 题：计算数组的逆序对；
• 官方题解链接（有视频讲解）：数组中的逆序对；
• 题解链接：暴力解法、分治思想、树状数组。

在数组中的两个数字如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。

输入一个数组，求出这个数组中的逆序对的总数。

样例

输入：[1,2,3,4,5,6,0]

输出：6

方法一：根据定义

首先我们应该想到，使用定义计算逆序数，时间复杂度是：$O(n^2)$。

Java 代码：

public class Solution {

    public int reversePairs(int[] nums) {
        int cnt = 0;
        int len = nums.length;
        for (int i = 0; i < len - 1; i++) {
            for (int j = i + 1; j < len; j++) {
                if (nums[i] > nums[j]) {
                    cnt++;
                }
            }
        }
        return cnt;
    }
}

Python 代码：

class Solution(object):
    def inversePairs(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

方法二：分治算法（借助归并排序）

这种思路虽然很直接，但编写出错的概率就很低了，在没有在线评测系统的时候，它可以作为一个「正确的」参考答案，用以检验我们自己编写的算法是否正确。

思路2：借助归并排序的分治思想，时间复杂度为 $O(n \log n)$。

分析：例如：前有序数组：$[2,3,5,8]$，后有序数组：$[4,6,7,12]$。

做归并的时候，步骤如下：

第 1 步，$2$ 先出列，$2$ 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 2 步，$3$ 出列，$3$ 比“后有序数组”中所有的元素都小，构成“顺序对”；

第 3 步，$4$ 出列，关键的地方在这里，“前有序数组”中所有剩下的元素 $[5,8]$ 比 $4$ 都大，构成 $2$ 个 “逆序对”；

第 4 步，$5$ 出列，$5$ 比“后有序数组”中所有剩下的元素都小，构成“顺序对”；

第 5 步，$6$ 出列，“前有序数组”中所有剩下的元素 $[8]$ 比 $6$ 都大，构成 $1$ 个“逆序对”；

第 6 步，$7$ 出列，“前有序数组”中所有剩下的元素 $[8]$ 比 $7$ 都大，构成 $1$ 个“逆序对”；

第 7 步，$8$ 出列，$8$ 比“后有序数组”中所有剩下的元素 $[8]$ 都小，构成 $1$ 个“顺序对”；

第 8 步，$12$ 出列，此时“前有序数组”为空。

因此，我们只需要在“前有序数组”非空，且“后有序数组”中有元素出列的时候，即上面的第 3、5、6 步计算“逆序对”就可以了。

Java 代码：

public class Solution {

    public int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }

        int[] copy = new int[len];
        for (int i = 0; i < len; i++) {
            copy[i] = nums[i];
        }

        int[] temp = new int[len];
        return reversePairs(copy, 0, len - 1, temp);
    }

    /**
     * nums[left..right] 计算逆序对个数并且排序
     *
     * @param nums
     * @param left
     * @param right
     * @param temp
     * @return
     */
    private int reversePairs(int[] nums, int left, int right, int[] temp) {
        if (left == right) {
            return 0;
        }

        int mid = left + (right - left) / 2;
        int leftPairs = reversePairs(nums, left, mid, temp);
        int rightPairs = reversePairs(nums, mid + 1, right, temp);

        // 如果整个数组已经有序，则无需合并，注意这里使用小于等于
        if (nums[mid] <= nums[mid + 1]) {
            return leftPairs + rightPairs;
        }

        int crossPairs = mergeAndCount(nums, left, mid, right, temp);
        return leftPairs + rightPairs + crossPairs;
    }

    /**
     * nums[left..mid] 有序，nums[mid + 1..right] 有序
     *
     * @param nums
     * @param left
     * @param mid
     * @param right
     * @param temp
     * @return
     */
    private int mergeAndCount(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }

        int i = left;
        int j = mid + 1;

        int count = 0;
        for (int k = left; k <= right; k++) {
            // 有下标访问，得先判断是否越界
            if (i == mid + 1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right + 1) {
                nums[k] = temp[i];
                i++;
            } else if (temp[i] <= temp[j]) {
                // 注意：这里是 <= ，写成 < 就不对，请思考原因
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;

                // 在 j 指向的元素归并回去的时候，计算逆序对的个数，只多了这一行代码
                count += (mid - i + 1);
            }
        }
        return count;
    }
}

Python 代码：

class Solution(object):
    def inversePairs1(self, nums):
        l = len(nums)
        if l < 2:
            return 0
        res = 0
        for i in range(0, l - 1):
            for j in range(i + 1, l):
                if nums[i] > nums[j]:
                    res += 1
        return res

    def inversePairs(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """

        l = len(nums)
        if l < 2:
            return 0
        temp = [0 for _ in range(l)]
        return self.count_inversion_pairs(nums, 0, l - 1, temp)

    def count_inversion_pairs(self, nums, l, r, temp):
        """
        在数组 nums 的区间 [l,r] 统计逆序对
        :param nums:
        :param l: 待统计数组的左边界，可以取到
        :param r: 待统计数组的右边界，可以取到
        :param temp:
        :return:
        """
        # 极端情况下，就是只有 1 个元素的时候
        if l == r:
            return 0
        mid = l + (r - l) // 2
        left_pairs = self.count_inversion_pairs(nums, l, mid, temp)
        right_pairs = self.count_inversion_pairs(nums, mid + 1, r, temp)

        merge_pairs = 0
        # 代码走到这里的时候，
        # [l, mid] 已经完成了排序并且计算好逆序对
        # [mid + 1, r] 已经完成了排序并且计算好逆序对
        # 如果 nums[mid] <= nums[mid + 1]，此时就不存在逆序对
        # 当 nums[mid] > nums[mid + 1] 的时候，就要继续计算逆序对
        if nums[mid] > nums[mid + 1]:
            # 在归并的过程中计算逆序对
            merge_pairs = self.merge_and_count(nums, l, mid, r, temp)
        # 走到这里有 nums[mid] <= nums[mid + 1] 成立，已经是顺序结构
        return left_pairs + right_pairs + merge_pairs

    def merge_and_count(self, nums, l, mid, r, temp):
        """
        前：[2,3,5,8]，后：[4,6,7,12]
        我们只需要在后面数组元素出列的时候，数一数前面这个数组还剩下多少个数字，
        因为"前"数组和"后"数组都有序，
        因此，"前"数组剩下的元素个数 mid - i + 1 就是与"后"数组元素出列的这个元素构成的逆序对个数

        """
        for i in range(l, r + 1):
            temp[i] = nums[i]
        i = l
        j = mid + 1
        res = 0
        for k in range(l, r + 1):
            if i > mid:
                nums[k] = temp[j]
                j += 1
            elif j > r:
                nums[k] = temp[i]
                i += 1
            elif temp[i] <= temp[j]:
                # 不统计逆序对，只做排序
                nums[k] = temp[i]
                i += 1
            else:
                assert temp[i] > temp[j]
                nums[k] = temp[j]
                j += 1
                # 快就快在这里，一次可以数出一个区间的个数的逆序对
                # 例：[7,8,9][4,6,9]，4 与 7 以及 7 前面所有的数都构成逆序对
                res += (mid - i + 1)
        return res

说明：归并两个有序数组的时候，我们要借助额外的辅助空间，为此可以全局使用一个和原始数组等长的辅助数组，否则每一次进入 merge 函数都要 new 新数组，开销很大。

上述解法的缺点是修改了原始数组，排序完成以后，逆序数就计算出来了。为此：1、我们可以引入一个索引数组；2、或者直接拷贝一个原始数组，这样就不用修改原始数组了。

例2：「力扣」第 315 题：计算右侧小于当前元素的个数

传送门：315. 计算右侧小于当前元素的个数。

给定一个整数数组 nums，按要求返回一个新数组 *counts。数组 *counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例:

输入: [5,2,6,1]
输出: [2,1,1,0] 
解释:
5 的右侧有 2 个更小的元素 (2 和 1).
2 的右侧仅有 1 个更小的元素 (1).
6 的右侧有 1 个更小的元素 (1).
1 的右侧有 0 个更小的元素.

Java 代码：

import java.util.ArrayList;
import java.util.List;

public class Solution {

    private int[] temp;
    private int[] counter;
    private int[] indexes;

    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<>();
        int len = nums.length;
        if (len == 0) {
            return res;
        }
        temp = new int[len];
        counter = new int[len];
        indexes = new int[len];
        for (int i = 0; i < len; i++) {
            indexes[i] = i;
        }
        mergeAndCountSmaller(nums, 0, len - 1);
        for (int i = 0; i < len; i++) {
            res.add(counter[i]);
        }
        return res;
    }

    /**
     * 针对数组 nums 指定的区间 [l, r] 进行归并排序，在排序的过程中完成统计任务
     *
     * @param nums
     * @param l
     * @param r
     */
    private void mergeAndCountSmaller(int[] nums, int l, int r) {
        if (l == r) {
            // 数组只有一个元素的时候，没有比较，不统计
            return;
        }
        int mid = l + (r - l) / 2;
        mergeAndCountSmaller(nums, l, mid);
        mergeAndCountSmaller(nums, mid + 1, r);
        // 归并排序的优化，同样适用于该问题
        // 如果索引数组有序，就没有必要再继续计算了
        if (nums[indexes[mid]] > nums[indexes[mid + 1]]) {
            mergeOfTwoSortedArrAndCountSmaller(nums, l, mid, r);
        }
    }

    /**
     * [l, mid] 是排好序的
     * [mid + 1, r] 是排好序的
     *
     * @param nums
     * @param l
     * @param mid
     * @param r
     */
    private void mergeOfTwoSortedArrAndCountSmaller(int[] nums, int l, int mid, int r) {
        // 3,4  1,2
        for (int i = l; i <= r; i++) {
            temp[i] = indexes[i];
        }
        int i = l;
        int j = mid + 1;
        // 左边出列的时候，计数
        for (int k = l; k <= r; k++) {
            if (i > mid) {
                indexes[k] = temp[j];
                j++;
            } else if (j > r) {
                indexes[k] = temp[i];
                i++;
                // 此时 j 用完了，[7,8,9 | 1,2,3]
                // 之前的数就和后面的区间长度构成逆序
                counter[indexes[k]] += (r - mid);
            } else if (nums[temp[i]] <= nums[temp[j]]) {
                indexes[k] = temp[i];
                i++;
                // 此时 [4,5, 6   | 1,2,3 10 12 13]
                //           mid          j
                counter[indexes[k]] += (j - mid - 1);
            } else {
                // nums[indexes[i]] > nums[indexes[j]] 构成逆序
                indexes[k] = temp[j];
                j++;
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{5, 2, 6, 1};
        Solution solution = new Solution();
        List<Integer> countSmaller = solution.countSmaller(nums);
        System.out.println(countSmaller);
    }
}

Python 代码：

class Solution:
    def countSmaller(self, nums):
        """
        :type nums: List[int]
        :rtype: List[int]
        """

        size = len(nums)
        if size == 0:
            return []
        if size == 1:
            return [0]

        temp = [None for _ in range(size)]
        indexes = [i for i in range(size)]
        res = [0 for _ in range(size)]

        self.__helper(nums, 0, size - 1, temp, indexes, res)
        return res

    def __helper(self, nums, left, right, temp, indexes, res):
        if left == right:
            return
        mid = left + (right - left) // 2

        # 计算一下左边
        self.__helper(nums, left, mid, temp, indexes, res)
        # 计算一下右边
        self.__helper(nums, mid + 1, right, temp, indexes, res)

        if nums[indexes[mid]] <= nums[indexes[mid + 1]]:
            return
        self.__sort_and_count_smaller(nums, left, mid, right, temp, indexes, res)

    def __sort_and_count_smaller(self, nums, left, mid, right, temp, indexes, res):
        # [left,mid] 前有序数组
        # [mid+1,right] 后有序数组

        # 先拷贝，再合并

        for i in range(left, right + 1):
            temp[i] = indexes[i]

        l = left
        r = mid + 1
        for i in range(left, right + 1):
            if l > mid:
                # l 用完，就拼命使用 r
                # [1,2,3,4] [5,6,7,8]
                indexes[i] = temp[r]
                r += 1
            elif r > right:
                # r 用完，就拼命使用 l
                # [6,7,8,9] [1,2,3,4]
                indexes[i] = temp[l]
                l += 1
                # 注意：此时前面剩下的数，比后面所有的数都大
                res[indexes[i]] += (right - mid)
            elif nums[temp[l]] <= nums[temp[r]]:
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[l]
                l += 1
                # 注意：
                res[indexes[i]] += (r - mid - 1)
            else:
                assert nums[temp[l]] > nums[temp[r]]
                # 上面两种情况只在其中一种统计就可以了
                # [3,5,7,9] [4,6,8,10]
                indexes[i] = temp[r]
                r += 1

说明：这里用到了一个索引数组 indeses，是一个常见的技巧。比如我们交换数组的元素成本很大的时候，可以使用索引数组，交换索引成本很低。这一点，在我们以后介绍索引堆的时候还会用到。

例3：「力扣」第 53 题：最大子序和

• 中文网址：53. 最大子序和 ；

• 英文网址：53. Maximum Subarray ；

• 题解链接：动态规划、分治法。

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:

输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大，为 6。

进阶:

如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

分析：这道题其实最先应该想到使用动态规划，使用分治有点“小题大作”，我们不妨把分治解法看做一个例题。

分治的时候，要注意一点，不重不漏。

Python 代码：

class Solution(object):
    def maxSubArray(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        n = len(nums)
        if n == 0:
            return 0
        return self.__max_sub_array(nums, 0, n - 1)

    def __max_sub_array(self, nums, left, right):
        if left == right:
            return nums[left]
        mid = left + (right - left) // 2
        return max(self.__max_sub_array(nums, left, mid),
                   self.__max_sub_array(nums, mid + 1, right),
                   self.__max_cross_array(nums, left, mid, right))

    def __max_cross_array(self, nums, left, mid, right):
        """
        一定包含 nums[mid] 元素的最大连续子数组的和
        思路是看看左边扩散到底，得到一个最大数
        右边扩散到底得到一个最大数
        :param nums:
        :param mid:
        :param right:
        :return:
        """
        ls = 0
        j = mid - 1
        s1 = 0
        while j >= left:
            s1 += nums[j]
            ls = max(ls, s1)
            j -= 1

        rs = 0
        j = mid + 1
        s2 = 0
        while j <= right:
            s2 += nums[j]
            rs = max(rs, s2)
            j += 1

        return ls + nums[mid] + rs


if __name__ == '__main__':
    s = Solution()
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    result = s.maxSubArray(nums)
    print(result)

（本节完）