315. 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数

给定一个整数数组 nums，按要求返回一个新数组 counts。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

思路

归并排序

在归并排序中统计依次统计左路元素大于右路元素的个数，注意一个优化技巧，由于左右路元素已经排序完毕，在统计左路元素大于右路元素时，统计左路元素下一个时，r指针无需归位，因为左路元素已经按从小到大排序。

代码

class Solution {
   
public:
    vector<int> countSmaller(vector<int>& nums) {
   
        int n = nums.size();
        vector<pair<int, int>> v;
        vector<int> ans(n, 0);
        for(int i = 0; i < n; i++) {
   
            v.push_back(make_pair(nums[i], i));
        }
        mergesort(v, ans, 0, n - 1);
        return ans;
    }

    void mergesort(vector<pair<int, int>>& v, vector<int>& ans, int left, int right) {
   
        if(left >= right) {
   
            return ;
        }
        int mid = left + (right - left) / 2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22