一、小和問題

問題描述，給定一個數組，如[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的左右兩組一定是有序的，在左組數較小并拷貝時計算右組中大于自己的數的個數乘以自身就，就可以得到一個當前范圍內右側累計值：

上圖是一個常規的非對稱情況的 merge 操作，其中 1 3 已經通過merge排好序（盡管已經是有序的，但也會執行一次merge）。

在merge的時候，左組拷貝產生小和，右組拷貝不產生小和。根據之前的逆向思路，我們需要計算每個數右組比自己大的元素個數，由于已經有了“左右兩組各自有序”這個前提，因此在copy左組元素的時候，直接取右組當前比較的位置到 R 的元素個數即可，而當左右兩組當前比較的元素相等時，我們必須先拷貝右組元素，這是為了方便計算右組有幾個數大于左組：

實現及測試完整代碼：

/*** 小和問題*/ 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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 testpublic 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/

提議描述：給定一個數組 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 位置左側達標的元素并計數，最終就一定會統計出全部達標的子數組個數。

上圖中，移位換項指的是? 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;} }

?

?

總結

以上是生活随笔為你收集整理的排序算法——归并排序的相关问题的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。