排序算法——归并排序的相关问题

小灰灰 2023-01-13 09:35 115阅读 0赞

# 一、小和问题 #

问题描述，给定一个数组，如\[1, 3, 2, 6, 5\]，计算每个数左边小于自己的所有数的和，并累加。例如：

> 1左边没有数
> 
> 3左边有一个小于自己的数 1
> 
> 2左边有一个小于自己的数 1
> 
> 6左边有三个小于自己的数 1 + 3 + 2 = 6
> 
> 5左边有三个小于自己的数 1 + 3 + 2 = 6
> 
> 最后 1 + 1 + 6 + 6 = 14，上面给定数组 \[1, 3, 2, 6, 5\] 的小和解就是 14.

解题思路：这道题的常规思路是循环每个数，然后再遍历它左边的所有数，只要比自己小，就累加到 sum 上。时间复杂度是 O(N^2)。

如何将它改写成 O(N^logN)复杂度的算法？可以利用递归。

本题中我们要计算每个数左侧小于自己数的和，反过来看，就是每个数算一下右边有几个大于自己的数，然后求和。还是以上面的数组为例：

> 1右边有四个数大于自己，4 \* 1 = 4
> 
> 3右边有两个数大于自己，2 \* 3 = 6
> 
> 2右边有两个数大于自己，2 \* 2 = 4
> 
> 6右边没有大于自己的数
> 
> 5右边没有大于自己的数
> 
> 最后 4 + 6 + 4 = 14，和前一种按照题意原本的规则计算的结果完全一致。

有了这个逆向思路，我们可以在归并排序 merge 的时候，由于merge的左右两组一定是有序的，在左组数较小并拷贝时计算右组中大于自己的数的个数乘以自身就，就可以得到一个当前范围内右侧累计值：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70][]

上图是一个常规的非对称情况的 merge 操作，其中 1 3 已经通过merge排好序（尽管已经是有序的，但也会执行一次merge）。

在merge的时候，**左组拷贝产生小和，右组拷贝不产生小和**。根据之前的逆向思路，我们需要计算每个数右组比自己大的元素个数，由于已经有了“左右两组各自有序”这个前提，因此在copy左组元素的时候，直接取右组当前比较的位置到 R 的元素个数即可，而当左右两组当前比较的元素相等时，我们必须先拷贝右组元素，这是为了方便计算右组有几个数大于左组：

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1][]

实现及测试完整代码：

/**
     * 小和问题
     */
    public class Code2_SmallSum {
    
        public static int smallSum(int[] arr) {
            if (arr == null || arr.length < 2)
                return 0;
            return process(arr, 0, arr.length - 1);
        }
    
        private static int process(int[] arr, int L, int R) {
            if (L == R)
                return 0;
            int M = L + ((R - L) >> 1);
            int leftSum = process(arr, L, M);
            int rightSum = process(arr, M + 1, R);
            int mergeSum = merge(arr, L, M, R);
            return leftSum + rightSum + mergeSum;
        }
    
        private static int merge(int[] arr, int L, int M, int R) {
            int[] help = new int[R - L + 1];
            int p1 = L;
            int p2 = M + 1;
            int i = 0;
            int res = 0;
            while (p1 <= M && p2 <= R) {
                res += arr[p1] < arr[p2] ? (R - p2 + 1) * arr[p1] : 0;
                help[i++] = arr[p1] < arr[p2] ? arr[p1++] : arr[p2++];
            }
            while (p1 <= M) {
                help[i++] = arr[p1++];
            }
            while (p2 <= R) {
                help[i++] = arr[p2++];
            }
            for (i = 0; i < help.length; i++) {
                arr[L + i] = help[i];
            }
            return res;
        }
    
    
        // for test
        public static int comparator(int[] arr) {
            if (arr == null || arr.length < 2) {
                return 0;
            }
            int res = 0;
            for (int i = 1; i < arr.length; i++) {
                for (int j = 0; j < i; j++) {
                    res += arr[j] < arr[i] ? arr[j] : 0;
                }
            }
            return res;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            boolean succeed = true;
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                if (smallSum(arr1) != comparator(arr2)) {
                    succeed = false;
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println(succeed ? "Nice!" : "Fucking fucked!");
        }
    
    }

# 二、逆序对个数问题 #

逆序对个数是经典考题，也是常考题，它的问题是这样的：

给定一个数组，如 \[1, 3, 2, 6, 4\] ，在整个数组范围内，只要两个数形成降序，即判定为一个**逆序对**，统计这个数组的逆序对个数：

> 以上述数组为例，3, 2  和 6，4都是逆序对，因此该数组总共有两个逆序对。

题意非常好理解，同时它也是上题小和问题的一个变种，上面的小和问题通过逆向思维，实际上计算的是右侧有几个比自己大的数，然后累乘自身，而本题是求右侧有多少个比自己小，累加。

那么以升序排序的方式可以求右组比自己大的个数，同理，以降序排序的方式就可以求右组比自己小的个数。因此，只需要降序merge，并统计个数即可，完整代码和测试如下：

/**
     * 逆序对个数
     */
    public class Code2_ReversedPair {
    
        /**
         * 降序，再count
         */
        public static int reversedPairCount(int[] arr) {
            if (arr == null || arr.length < 2)
                return 0;
            return process(arr, 0, arr.length - 1);
        }
    
        private static int process(int[] arr, int L, int R) {
            if (L == R)
                return 0;
            int M = L + ((R - L) >> 1);
            return process(arr, L, M) + process(arr, M + 1, R) + merge(arr, L, M, R);
        }
    
        private static int merge(int[] arr, int L, int M, int R) {
            int[] help = new int[R - L + 1];
            int p1 = L;
            int p2 = M + 1;
            int i = 0;
            int count = 0;
            while (p1 <= M && p2 <= R) {
                count += arr[p1] > arr[p2] ? (R - p2 + 1) : 0;
                help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
            }
            while (p1 <= M) {
                help[i++] = arr[p1++];
            }
            while (p2 <= R) {
                help[i++] = arr[p2++];
            }
            for (i = 0; i < help.length; i++) {
                arr[L + i] = help[i];
            }
            return count;
        }
    
        // for test
        public static int comparator(int[] arr) {
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > arr[j]) {
                        ans++;
                    }
                }
            }
            return ans;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) (maxValue * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 100;
            int maxValue = 100;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
                int[] arr2 = copyArray(arr1);
                if (reversedPairCount(arr1) != comparator(arr2)) {
                    System.out.println("Oops!");
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    }

# 三、两倍大问题 #

两倍大问题，给定一个数组，如\[6, 7, 1, 3, 2\]，计算出每个数右侧比自身要小两倍还多的数的累计个数。

/**
     * 两倍大问题：统计数组中每个比右边几个数两倍还大。
     * 6 7 1 3 2，
     * 6比1、2 大两倍还多
     * 7比1、3、2大两倍还多
     * 因此总个数就是5个
     */
    public class Code4_BeggerTwice {
    
        public static int biggerTwice(int[] arr) {
            if (arr == null || arr.length < 2)
                return 0;
            int count = process(arr, 0, arr.length - 1);
            return count;
        }
    
        private static int process(int[] arr, int L, int R) {
            if (L == R)
                return 0;
            int M = L + ((R - L) >> 1);
            return process(arr, L, M) + process(arr, M + 1, R) + merge(arr, L, M, R);
        }
    
        private static int merge(int[] arr, int L, int M, int R) {
            int[] help = new int[R - L + 1];
            int i = 0;
            int p1 = L;
            int p2 = M + 1;
            int count = 0;
            // [M + 1, R]
            int windowR = M + 1;
            for (int j = L; j <= M; j++) {
                while (windowR <= R && arr[j] <= arr[windowR] * 2)
                    windowR++;
                count += R - windowR + 1;
            }
            while (p1 <= M && p2 <= R) {
                help[i++] = arr[p1] > arr[p2] ? arr[p1++] : arr[p2++];
            }
            while (p1 <= M) {
                help[i++] = arr[p1++];
            }
            while (p2 <= R) {
                help[i++] = arr[p2++];
            }
            for (i = 0; i < help.length; i++) {
                arr[L + i] = help[i];
            }
            return count;
        }
    
        // for test
        public static int comparator(int[] arr) {
            int ans = 0;
            for (int i = 0; i < arr.length; i++) {
                for (int j = i + 1; j < arr.length; j++) {
                    if (arr[i] > (arr[j] << 1)) {
                        ans++;
                    }
                }
            }
            System.out.println("arr2总数为：" + ans);
            return ans;
        }
    
        // for test
        public static int[] generateRandomArray(int maxSize, int maxValue) {
            int[] arr = new int[(int) ((maxSize + 1) * Math.random())];
            for (int i = 0; i < arr.length; i++) {
                arr[i] = (int) ((maxValue + 1) * Math.random()) - (int) ((maxValue + 1) * Math.random());
            }
            return arr;
        }
    
        // for test
        public static int[] copyArray(int[] arr) {
            if (arr == null) {
                return null;
            }
            int[] res = new int[arr.length];
            for (int i = 0; i < arr.length; i++) {
                res[i] = arr[i];
            }
            return res;
        }
    
        // for test
        public static boolean isEqual(int[] arr1, int[] arr2) {
            if ((arr1 == null && arr2 != null) || (arr1 != null && arr2 == null)) {
                return false;
            }
            if (arr1 == null && arr2 == null) {
                return true;
            }
            if (arr1.length != arr2.length) {
                return false;
            }
            for (int i = 0; i < arr1.length; i++) {
                if (arr1[i] != arr2[i]) {
                    return false;
                }
            }
            return true;
        }
    
        // for test
        public static void printArray(int[] arr) {
            if (arr == null) {
                return;
            }
            for (int i = 0; i < arr.length; i++) {
                System.out.print(arr[i] + " ");
            }
            System.out.println();
        }
    
        // for test
        public static void main(String[] args) {
            int testTime = 500000;
            int maxSize = 10;
            int maxValue = 10;
            System.out.println("测试开始");
            for (int i = 0; i < testTime; i++) {
                int[] arr1 = generateRandomArray(maxSize, maxValue);
    //            System.out.println("原始数组：==========");
    //            printArray(arr1);
                int[] arr2 = copyArray(arr1);
                if (biggerTwice(arr1) != comparator(arr2)) {
                    System.out.println("Oops!");
                    printArray(arr1);
                    printArray(arr2);
                    break;
                }
            }
            System.out.println("测试结束");
        }
    
    
    }

# 四、求区间和子数组个数 #

本题是LeetCode真题——327题区间和个数：[https://leetcode-cn.com/problems/count-of-range-sum/][https_leetcode-cn.com_problems_count-of-range-sum]

提议描述：给定一个数组 arr，两个整数 lower 和 upper，计算出 arr 中有多少个子数组的累加和在 \[lower, upper\] 范围上，要求子数组必须连续。

例如，\[1, 3, -2\] ，求累加和范围在 \[2, 4\] 范围上的子数组个数：

> \[1\] 不符合
> 
> \[1, 3\] **符合**
> 
> \[1, 3, -2\] **符合**
> 
> \[3\] **符合**
> 
> \[3, -2\] 不符合
> 
> \[-2\] 不符合
> 
> 所以，符合达标的子数组分别是\[1, 3\]、\[1, 3, -2\]、\[3\] ，共 3 个子数组。
> 
> 小提示：枚举子数组的方式有两种，一种是以头位置开始，上面就是这种方式，还有一种是以尾为标准，例如：
> 
> 以 0 位置结尾的子数组：\[1\]
> 
> 以 1 位置结尾的子数组：\[1, 3\]、\[3\]、
> 
> 以 2 位置结尾的子数组：\[1,3,-2\]、\[3, -2\]、\[-2\]

**解题思路：**这是一道困难难度的面试题。在解答本题之前，需要有一些转换技巧作为铺垫——**前缀和问题**。

前缀和问题的描述是，一个数组 arr\[\] ，元素是无序整数，正负0都有，给定一个 \[i, j\] 范围，求累加和。这个问题可以算得上是区间和问题的一个重要逻辑单元。

最傻瓜式的方式无非就是从 i 到 j 遍历元素，然后累加。如何优化？可以转变成“**前缀和问题**”。

求\[0, j\] 累加和，减去\[0，i - 1\] 范围的累加和，即可得到 \[i, j\] 范围的累加和。我们称之为“前缀和”，就是因为每个位置的前缀和都是从0位置开始一直加到自身位置，而每个位置上的前缀和只需要遍历一遍就可以轻松得出。

如果我们实现通过一次遍历得到了和原数组每个位置元素对应的前缀和，那么 \[i, j\] 累加和问题就可以轻松变为从前缀和数组中取 j 和 i 位置上的两个数，然后相减，抛去只执行一次的前缀和数组的生成，后面的每次操作都是常数时间复杂度，极大地提升了效率。

public static int rangeSum(int[] arr, int lower, int upper) {
            if (arr == null || lower < 0 || upper >= arr.length)
                throw new IllegalArgumentException("参数不合法");
            int[] preSum = new int[arr.length];
            preSum[0] = arr[0];
            for (int i = 1; i < arr.length; i++) {
                preSum[i] = preSum[i - 1] + arr[i];
            }
            return preSum[upper] - preSum[lower - 1];
        }

有了以上这些知识的铺垫，再来回看原题，**求累加和属于 \[lower, upper\] 范围的子数组个数**，如果有了原数组对应的前缀和数组，假设以 i 位置为例，求以 i 位置结尾的子数组累加和属于 \[lower, upper\] 范围，对应前缀和数组，就是求以 i 位置结尾的前缀和与多少个左侧前缀和相减的差属于\[lower, upper\] ，如果 i 位置上的前缀和为 x，那么这个 i 位置左侧的小前缀和的区间范围就应该落在与其互补的 \[x - upper, x - lower\] 范围上，简言之就是求前缀和数组上，i 位置左侧有多少个元素属于 \[x-upper, x - lower\] 范围，由于我们一定可以通过以各个位置上的数结尾的子数组穷举全部子数组，因此利用归并求出每个 i 位置左侧达标的元素并计数，最终就一定会统计出全部达标的子数组个数。

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 2][]

上图中，移位换项指的是  i - j = \[lower, upper\] ，将 j 移到一侧，得出 j = \[i - lower, i - upper\] 。

完整代码如下：

public class Code1_CountOfRangeSum {
    
        public static int countRangeSum(int[] arr, int lower, int upper) {
            if (arr == null || arr.length == 0)
                throw new IllegalArgumentException("参数非法！");
            long[] preSum = new long[arr.length];
            preSum[0] = arr[0];
            for (int i = 1; i < arr.length; i++) {
                preSum[i] = preSum[i - 1] + arr[i];
            }
            return process(preSum, 0, preSum.length - 1, lower, upper);
        }
    
        private static int process(long[] preSum, int L, int R, int lower, int upper) {
            if (L == R)
                return preSum[L] >= lower && preSum[L] <= upper ? 1 : 0;
            int M = L + ((R - L) >> 1);
            return process(preSum, L, M, lower, upper)
                    + process(preSum, M + 1, R, lower, upper)
                    + merge(preSum, L, M, R, lower, upper);
        }
    
        private static int merge(long[] preSum, int L, int M, int R, int lower, int upper) {
            int count = 0;
            int windowL = L;
            int windowR = L;
            // [windowL, windowR)
            for (int i = M + 1; i <= R; i++) {
                long min = preSum[i] - upper;
                long max = preSum[i] - lower;
                while (windowR <= M && preSum[windowR] <= max)
                    windowR++;
                while (windowL <= M && preSum[windowL] < min)
                    windowL++;
                count += windowR - windowL;
            }
            long[] help = new long[R - L + 1];
            int i = 0;
            int p1 = L;
            int p2 = M + 1;
            while (p1 <= M && p2 <= R) {
                help[i++] = preSum[p1] <= preSum[p2] ? preSum[p1++] : preSum[p2++];
            }
            while (p1 <= M)
                help[i++] = preSum[p1++];
            while (p2 <= R)
                help[i++] = preSum[p2++];
            for (i = 0; i < help.length; i++) {
                preSum[L + i] = help[i];
            }
            return count;
        }
    }

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70]: /images/20221022/8e18befea909458baa76fb029373fa7f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 1]: /images/20221022/0f44f531b3b240778da9ca61e717e5b5.png
[https_leetcode-cn.com_problems_count-of-range-sum]: https://leetcode-cn.com/problems/count-of-range-sum/
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3UwMTQ3NDUwNjk_size_16_color_FFFFFF_t_70 2]: /images/20221022/74c68798a49140dead9809c1a5bfe865.png