leetcode-315.计算右侧小于当前元素的个数_c++给你一个整数数组 nums,按要求返回一个新数组 counts。数组 counts有该性质 c

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

示例：

输入：[5,2,6,1]
输出：[2,1,1,0]
解释： 5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

考查树状数组的应用。
题意即求当前元素右侧且比当前元素小的元素个数，显然左侧元素的索引小于右侧元素。如果将元素按升序排序，则转化为求当前元素左侧且比当前元素的索引大的元素个数，这就是逆序数问题，可以采用树状数组求解。
注意最后要按索引升序排序，这样得到的元素序列才是原来输入的序列。
模拟两种情况：
case 1:

5 2 6 1
------------------
第一次排序前：
元素值：5 2 6 1
  下标：1 2 3 4
------------------
第一次排序后：
元素值：1 2 5 6
  下标：4 2 1 3
逆序数：0 1 2 1
------------------
第二次排序后：
元素值：5 2 6 1
  下标：1 2 3 4
逆序数：2 1 1 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

从第一次排序前的序列中我们可以看出5>2，但是(5的索引1)<(2的索引3)，对于任意的a>b，都有(a的索引)<(b的索引)
case 2:

5 2 6 2
------------------
第一次排序前：
元素值：5 2 6 2
  下标：1 2 3 4
------------------
第一次排序后：
元素值：2 2 5 6
  下标：2 4 1 3
逆序数：0 0 2 1
------------------
第二次排序后：
元素值：5 2 6 2
  下标：1 2 3 4
逆序数：2 0 1 0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意可能存在多个元素值相等的情况，要在第一次排序时保证元素相等时按索引升序排序。

typedef struct node{
    int val;//元素的值
    int index;//元素的索引（从1开始）
    int cnt;//第一次排序后该元素前面的所有逆序数对
}Node;
/*
cmp1函数：
按元素值从小到大排序，元素值相同时按索引从小到大排序
*/
int cmp1(const void*a,const void*b){
    Node*x=(Node*)a;
    Node*y=(Node*)b;
    if(x->val!=y->val){
        return x->val-y->val;
    }
    else{
        return x->index-y->index;
    }
}
/*
cmp2函数：
直接按元素的索引从小到大排序
*/
int cmp2(const void*a,const void*b){
    Node*x=(Node*)a;
    Node*y=(Node*)b;
    return x->index-y->index;
}
class Solution {
private:
    Node*counts;
    int *tree;
    int len;
public:
    vector<int> countSmaller(vector<int>& nums) {
        len=nums.size();
        tree=new int[len+5];//leetcode上的代码风格不同于ACM
        counts=new Node[len+5];
        for(int i=1;i<=len;i++){
            tree[i]=0;//别忘了初始化
            counts[i].val=nums[i-1];
            counts[i].index=i;
        }
        qsort(counts+1,len,sizeof(counts[1]),cmp1);//第一次排序
        for(int i=1;i<=len;i++){
            update(counts[i].index);
            counts[i].cnt=i-query(counts[i].index);
        }
        qsort(counts+1,len,sizeof(counts[1]),cmp2);//第二次排序
        vector<int>ans;
        for(int i=1;i<=len;i++){
            ans.push_back(counts[i].cnt);
        }
        return ans;
    }
    int lowbit(int x){
        return x&(-x);
    }
    void update(int pos){//树状数组——更新
        int i=pos;
        while(i<=len){
            tree[i]++;
            i+=lowbit(i);
        }
    }
    int query(int pos){//树状数组——查询（求和）
        int ans=0;
        while(pos>0){
            ans+=tree[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
};
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