LEETCODE 315. 计算右侧小于当前元素的个数(归并)

class Solution {
public:  // 将count声明为public
    vector<int> count; 
    vector<int> indexs,tmp;

public:

    vector<int> countSmaller(vector<int>& nums) {
        //归并
        int left=0;
        int right=nums.size()-1;

        //计数
        // vector<int> count(nums.size()); 

        count=vector<int>(nums.size());

        for(int i=0;i<nums.size();i++){
            count[i]=0;
        }
        //index    
        // vector<int> indexs(nums.size());

        indexs=vector<int>(nums.size());

        for(int i=0;i<nums.size();i++){
            indexs[i]=i;
        }

        tmp=vector<int>(nums.size());

        mergeSort(left,right,nums);
        // vector<int> counts;
        // for(int i=0;i<nums.size();i++)
        //     counts.push_back(n[nums_copy[i]]);
        return count;
    }
    void mergeSort(int left,int right,vector<int>& nums){
        if(left>=right)
            return ;
        int mid=left+(right-left)/2;
        mergeSort(left,mid,nums);
        mergeSort(mid+1,right,nums);
        merge(left,right,nums);
    }
    void merge(int left,int right,vector<int>& nums){
        int mid=left+(right-left)/2;
        int i=left;
        int j=mid+1;
        // vector<int> tmp;
        int k=0;
        while(i<=mid && j<=right){
            if(nums[indexs[i]]>nums[indexs[j]]){
                count[indexs[i]]+=(right-j)+1;
                tmp[k++]=indexs[i++];

            }
            else{
                tmp[k++]=indexs[j++];

            }
        }
        while(i<=mid){
            tmp[k++]=indexs[i++];
        }
        while(j<=right){
            tmp[k++]=indexs[j++];
        }
        for(int i=0;i<k;i++){
            indexs[left+i]=tmp[i];
        }
        // tmp.clear();
        
    }

};

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
64
65
66
67
68
69
70
71
72
73
74
75
76
77

Focus:
1 (int left,int right,vector& nums) &没有用取址符会超出内存
2 点在于indexs 按index顺序归并，比较按里面元素
3 tmp index count