題目鏈接

315. 計算右側小于當前元素的
個數 - 力扣（LeetCode）

題目解析

計算數組里面所有元素右側比它小的數的個數, 并且組成一個數組,進行返回

算法原理

歸并解法(分治)

當前元素的后面, 有多少個比我小(降序)

我們要找到第一比左邊小的元素, 這樣就可以找到一堆比左邊小的元素: right - cur2+1

nums[cur1]對應的位置,里面的ret[原始下標]+=right-cur2+1

此時我們就需要找到數組原始的下標,然后把數記上

我們使用一個數組的每一個元素來一一對應記錄nums每個元素的下標

然后在每一次歸并排序,排完后,下標也跟著變

細節問題, 在創建輔助數組進行合并的時候, 需要創建倆個輔助數組, 一個給nums,一個給index,因為倆個數組是同步改變的

代碼編寫

class Solution {int[] ret;//記錄結果int[] index; // 標記 nums 中當前元素的原始下標int[] tmpIndex;// 記錄臨時數組的值int[] tmpNums;//記錄臨時下標的值public List<Integer> countSmaller(int[] nums) {int n = nums.length;ret = new int[n];index = new int[n];tmpIndex = new int[n];tmpNums = new int[n];
// 初始化 index 數組for (int i = 0; i < n; i++)index[i] = i;mergeSort(nums, 0, n - 1);List<Integer> l = new ArrayList<Integer>();for (int x : ret)l.add(x);return l;}public void mergeSort(int[] nums, int left, int right) {if (left >= right) return;
// 1. 根據中間元素劃分區間int mid = (left + right) / 2;
// [left, mid] [mid + 1, right]
// 2. 處理左右兩個區間mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);
// 3. 處理?左?右的情況int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right) // 降序排序{if (nums[cur1] <= nums[cur2]) {tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];} else {ret[index[cur1]] += right - cur2 + 1; // 重點tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}}
// 4. 處理剩余的排序?作while (cur1 <= mid) {tmpNums[i] = nums[cur1];tmpIndex[i++] = index[cur1++];}while (cur2 <= right) {tmpNums[i] = nums[cur2];tmpIndex[i++] = index[cur2++];}for (int j = left; j <= right; j++) {nums[j] = tmpNums[j - left];index[j] = tmpIndex[j - left];}}
}