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

要求：rt
思路：逆序对加强版，相当于统计每个位置的逆序对，树状数组线段树不会，归并。nums是归并数组，sort_nums是归并的临时数组（每次归并完复制到nums）。用pair右边存下标，归并时比较nums.first，存到sort_nums，逆序按nums.second计算。这里逆序跟之前那道题用的不一样，这里要算每个数产生的逆序：归并左边数组nums[i]<=nums[j]时，说明nums[i]跟j之前的都逆序，最后剩下i没j了要算整个右边数组。
如果不用pair，就像题解那些用索引数组的，归并前我们有一个pair的nums，归并时有一个临时的pair的sort_nums，那么相应的归并前要有索引数组和数数组，归并时要建他们的临时数组。类似的，index[j]表示任何时刻nums[j]的初始下标，有点绕

class Solution {
public:
    vector<int> res;
    vector<int> countSmaller(vector<int>& vec) {
        if (vec.empty())return {};
        vector<pair<int, int>> nums;
        for (int i = 0; i < vec.size(); i++)
            nums.emplace_back(vec[i], i);
        res = vector<int>(vec.size(), 0);
        merge_sort(nums, 0, (int)nums.size() - 1);
        return res;
    }
    void merge_sort(vector<pair<int, int>>& nums, int left, int right){
        if (left >= right)return;
        int mid = left + (right - left) / 2;
        merge_sort(nums, left, mid);
        merge_sort(nums, mid + 1, right);
        merge(nums, left, mid, right);
    }
    void merge(vector<pair<int, int>>& nums, int left, int mid, int right){
        int i = left, j = mid + 1;
        int index=0;
        vector<pair<int, int>> sort_nums(right-left+1);
        while (i <= mid && j <= right){
            if (nums[i].first <= nums[j].first){
                res[nums[i].second] += j - mid - 1;
                sort_nums[index++]=nums[i++];
            }else sort_nums[index++]=nums[j++];
        }
        while (i <= mid){
            res[nums[i].second] += j - mid - 1;
            sort_nums[index++]=nums[i++];
        }
        while (j <= right)
            sort_nums[index++]=nums[j++];
        for(int i=0;i<sort_nums.size();++i)
            nums[i+left]=sort_nums[i];
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

参考

class Solution {
public:
    vector<int> index;//用于解决排序后原数组元素顺序变更问题

    void merge(vector<int> &nums,int left,int mid,int right,vector<int> &res)
    {
        int n=right-left+1;
        int *tmp=new int[n],*tempIndex=new int[n];
        int tmpPos=0;
        int leftPos=left,rightPos=mid+1;
        while(leftPos<=mid && rightPos<=right)
        {
            if(nums[leftPos]>nums[rightPos])//数组降序排列
            {
                res[index[leftPos]]+=right-rightPos+1;//用下标直接计算排序好的右半部分小于nums[leftPos]元素的数目
                tempIndex[tmpPos]=index[leftPos];//记录元素位置的改变，与排序思想相同
                tmp[tmpPos++]=nums[leftPos++];
            }
            else//nums[leftPos]<=nums[rightPos]，等号放在这里是为了更方便上面计算right-rightPos+1这个数目
            {
                tempIndex[tmpPos]=index[rightPos];//记录元素位置的改变，与排序思想相同
                tmp[tmpPos++]=nums[rightPos++];
            }
        }
        while(leftPos<=mid)
        {
            tempIndex[tmpPos]=index[leftPos];
            tmp[tmpPos++]=nums[leftPos++];
        }
            
        while(rightPos<=right)
        {
            tempIndex[tmpPos]=index[rightPos];
            tmp[tmpPos++]=nums[rightPos++];
        }
            
        for(int i=0;i<n;++i)
        {
            nums[left+i]=tmp[i];
            index[left+i]=tempIndex[i];
        }
        delete[] tmp;
        delete[] tempIndex;
    }
    void mergesort(vector<int> &nums,int left,int right,vector<int> &res)
    {
        if(left==right) return;
        int mid=(right-left)/2+left;
        mergesort(nums,left,mid,res);
        mergesort(nums,mid+1,right,res);
        merge(nums,left,mid,right,res);
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> res(nums.size(),0);
        index.resize(nums.size());
        for(int i=0;i<nums.size();++i) index[i]=i;
        mergesort(nums,0,nums.size()-1,res);
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60