文章目錄

• 1 題目理解
• 2 暴力解法
• 3 分治法

1 題目理解

輸入：int[] nums
輸出：計數的數組int[] counts
規則：counts[i]表示nums中下標大于i，值小于nums[i]的個數
Example 1:
Input: nums = [5,2,6,1]
Output: [2,1,1,0]
Explanation:
To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

2 暴力解法

對于處理每個元素nums[i]，依次數一數從i+1到n，小于nums[i]的數有多少個。

class Solution {public List<Integer> countSmaller(int[] nums) {List<Integer> list = new ArrayList<Integer>();for(int i=0;i<nums.length;i++){int c = 0;for(int j=i+1;j<nums.length;j++){if(nums[j]<nums[i]){c++;}}list.add(c);}return list;} }

時間復雜度$O(n^2)$

3 分治法

以下內容來自力扣官網。
數一數在右側，比自己小的元素個數，這實際上就是在求逆序對。在學習算法過程中遇到過，利用歸并排序計算逆序對個數。

我們還是要在「歸并排序」的「并」中做文章。我們通過一個實例來看看。假設我們有兩個已排序的序列等待合并，分別是 L = { 8, 12, 16, 22, 100 } 和 R = { 7, 26, 55, 64, 91 }。一開始我們用指針 lPtr = 0 指向 L 的頭部，rPtr = 0 指向 R 的頭部。記已經合并好的部分為 M。

我們發現 lPtr 指向的元素大于 rPtr 指向的元素，于是把 rPtr 指向的元素放入答案，并把 rPtr 后移一位。

接著我們繼續合并：

此時 lPtr 比 rPtr 小，把 lPtr 對應的數加入答案。如果我們要統計 8 的右邊比 8 小的元素，這里 7 對它做了一次貢獻。如果待合并的序列 L = { 8, 12, 16, 22, 100 }，R = { 7, 7, 7, 26, 55, 64, 91}，那么一定有一個時刻，lPtr 和 rPtr 分別指向這些對應的位置：

下一步我們就是把 8 加入 M 中，此時三個 7 對 8 的右邊比 8 小的元素的貢獻為 3。以此類推，我們可以一邊合并一邊計算 R 的頭部到 rPtr 前一個數字對當前 lPtr 指向的數字的貢獻。

我們發現用這種「算貢獻」的思想在合并的過程中計算逆序對的數量的時候，只在 lPtr 右移的時候計算，是基于這樣的事實：當前 lPtr 指向的數字比 rPtr 小，但是比 R 中 [0 … rPtr - 1] 的其他數字大，[0 … rPtr - 1] 的數字是在 lPtr 右邊但是比 lPtr 對應數小的數字，貢獻為這些數字的個數。

但是我們又遇到了新的問題，在「并」的過程中 88 的位置一直在發生改變，我們應該把計算的貢獻保存到哪里呢？這個時候我們引入一個新的數組，來記錄每個數字對應的原數組中的下標，例如：

排序的時候原數組和這個下標數組同時變化，則排序后我們得到這樣的兩個數組：

我們用一個數組 ans 來記錄貢獻。我們對某個元素計算貢獻的時候，如果它對應的下標為 p，我們只需要在 ans[p] 上加上貢獻即可。

class Solution {private int[] index;private int[] temp;private int[] tempIndex;private int[] ans;private Map<Integer,Integer> valueIndexMap;public List<Integer> countSmaller(int[] nums) {this.index = new int[nums.length];this.temp = new int[nums.length];this.tempIndex = new int[nums.length];this.ans = new int[nums.length];valueIndexMap = new HashMap<Integer,Integer>();for(int i=0;i<nums.length;i++){valueIndexMap.put(nums[i],i);}for (int i = 0; i < nums.length; ++i) {index[i] = i;}int l = 0, r = nums.length - 1;mergeSort(nums, l, r);List<Integer> list = new ArrayList<Integer>();for (int num : ans) {list.add(num);}return list;}public void mergeSort(int[] a, int l, int r) {if (l >= r) {return;}int mid = (l + r) >> 1;mergeSort(a, l, mid);mergeSort(a, mid + 1, r);merge(a, l, mid, r);}public void merge(int[] a, int l, int mid, int r) {int i = l, j = mid + 1, p = l;while (i <= mid && j <= r) {if (a[i] <= a[j]) {temp[p] = a[i];tempIndex[p] = index[i];ans[valueIndexMap.get(a[i])] += (j - mid - 1);++i;++p;} else {temp[p] = a[j];tempIndex[p] = index[j];++j;++p;}}while (i <= mid) {temp[p] = a[i];tempIndex[p] = index[i];ans[valueIndexMap.get(a[i])] += (j - mid - 1);++i;++p;}while (j <= r) {temp[p] = a[j];tempIndex[p] = index[j];++j;++p;}for (int k = l; k <= r; ++k) {index[k] = tempIndex[k];a[k] = temp[k];}} }

時間復雜度$O(nlogn)$

總結

以上是生活随笔為你收集整理的315. Count of Smaller Numbers After Self的全部內容，希望文章能夠幫你解決所遇到的問題。

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