Leetcode 315. 计算右侧小于当前元素的个数（DAY 194）---- 归并算法学习期_leetcode315 c++ 归并

原题题目

代码实现（首刷自解 归并难题）

class Solution {
public:
    void merge(vector<int>& nums,vector<int>& tmp,vector<int>& precount,vector<int>& count,vector<int>& nowpos,vector<int>& prepos,int left,int right)
    {
        int l = left,mid = (left + (right - left) / 2),r = mid + 1,pos = l;
        while(l <= mid && r <= right)
        {
            if(nums[l] <= nums[r])
            {
                precount[pos] = count[l] + (r - mid - 1);   
                nowpos[pos] = prepos[l];   
                tmp[pos++] = nums[l++];
            }
            else
            {
                precount[pos] = count[r];  
                nowpos[pos] = prepos[r]; 
                tmp[pos++] = nums[r++];
            }
        }

        while(l <= mid)
        {
            precount[pos] = count[l] + (r - mid - 1); 
            nowpos[pos] = prepos[l];           
            tmp[pos++] = nums[l++];
        }
        
        while(r <= right)
        {
            precount[pos] = count[r];   
            nowpos[pos] = prepos[r]; 
            tmp[pos++] = nums[r++];
        }

        for(int i = left;i <= right;++i)
        {
            nums[i] = tmp[i];
            count[i] = precount[i];
            prepos[i] = nowpos[i];
        }
    }

    void merge_nums(vector<int>& nums,vector<int>& tmp,vector<int>& precount,vector<int>& count,vector<int>& nowpos,vector<int>& prepos,int left,int right)
    {
        if(left >= right) return;
        int mid = (left + (right - left) / 2);
        merge_nums(nums,tmp,precount,count,nowpos,prepos,left,mid);
        merge_nums(nums,tmp,precount,count,nowpos,prepos,mid + 1,right);
        merge(nums,tmp,precount,count,nowpos,prepos,left,right);  
    }

    vector<int> countSmaller(vector<int>& nums) {
        vector<int> idx(nums.size(),0),tmp(idx),count(idx),prepos(idx);
        vector<int> precount(idx),nowpos(idx);
        iota(prepos.begin(),prepos.end(),0);
        merge_nums(nums,tmp,precount,count,nowpos,prepos,0,tmp.size()-1);

        for(int i = 0;i < nums.size();++i)
            tmp[prepos[i]] = count[i];
        return tmp;
    }
};
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
61
62
63