目錄

315. 計算右側小于當前元素的個數

解析代碼

---

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

315. 計算右側小于當前元素的個數

難度 困難

給你一個整數數組?nums?，按要求返回一個新數組?counts?。數組?counts?有該性質：?counts[i]?的值是??nums[i]?右側小于?nums[i]?的元素的數量。

示例 1：

輸入：nums = [5,2,6,1]
輸出：[2,1,1,0] 
解釋：
5 的右側有 2 個更小的元素 (2 和 1)
2 的右側僅有 1 個更小的元素 (1)
6 的右側有 1 個更小的元素 (1)
1 的右側有 0 個更小的元素

示例 2：

輸入：nums = [-1]
輸出：[0]

示例 3：

輸入：nums = [-1,-1]
輸出：[0,0]

提示：

• 1 <= nums.length <= 10^5
• -10^4 <= nums[i] <= 10^4

class Solution {
public:vector<int> countSmaller(vector<int>& nums) {};

---

解析代碼

class Solution {vector<int> ret;vector<int> index; // nums中元素的原始下標vector<int> tmp_nums;vector<int> tmp_index; // 和nums里的元素綁定一起移動
public:vector<int> countSmaller(vector<int>& nums) {int n = nums.size();ret.resize(n);index.resize(n);tmp_nums.resize(n);tmp_index.resize(n);for (int i = 0; i < n; ++i){index[i] = i;}mergeSortCnt(nums, 0, n - 1);return ret;}void mergeSortCnt(vector<int>& nums, int left, int right){if (left >= right)return;int mid = (left + right) >> 1;mergeSortCnt(nums, left, mid);mergeSortCnt(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, i = 0;while (cur1 <= mid && cur2 <= right){if (nums[cur1] > nums[cur2]){ret[index[cur1]] += (right - cur2 + 1);tmp_nums[i] = nums[cur1];tmp_index[i++] = index[cur1++];}else{tmp_nums[i] = nums[cur2];tmp_index[i++] = index[cur2++];}}while (cur1 <= mid){tmp_nums[i] = nums[cur1];tmp_index[i++] = index[cur1++];}while (cur2 <= right){tmp_nums[i] = nums[cur2];tmp_index[i++] = index[cur2++];}for (int j = left; j <= right; ++j){nums[j] = tmp_nums[j - left];index[j] = tmp_index[j - left];}}
};