LeetCode-315-计算右侧小于当前元素的个数_leetcode 315

1、树状数组

具体实现可参考LeetCode-剑指51-数组中的逆序对。考虑到数组的长度范围过大，我们调用函数Discretization，首先对数组进行去重操作并保存在a中，并构建函数getId用于获得元素值与对应序号之间的映射关系。

而后我们初始化数组c，用于储存数组a的前缀和。我们只需要从后向前遍历数组nums，就可以利用getId找到其在数组c中的对应序号。而后我们只需要计算此时c中对应位置左侧的前缀和即可获得当前数组中既在nums[i]右侧又小于nums[i]的元素。值得注意的是，此处为了加快运算，我们使用二进制中末尾为 1 的位置进行加速查找。而后我们根据当前的序号对应更新c中的前缀和。考虑到我们是向数组末尾添加元素，我们最终对数组进行逆序操作即可。

class Solution {
private:
    vector<int> c;
    vector<int> a;

    void Init(int length) {
        c.resize(length, 0);
    }

    int LowBit(int x) {
        return x & (-x);
    }

    void Update(int pos) {
        while (pos < c.size()) {
            c[pos] += 1;
            pos += LowBit(pos);
        }
    }

    int Query(int pos) {
        int ret = 0;

        while (pos > 0) {
            ret += c[pos];
            pos -= LowBit(pos);
        }

        return ret;
    }

    void Discretization(vector<int>& nums) {
        a.assign(nums.begin(), nums.end());
        sort(a.begin(), a.end());
        a.erase(unique(a.begin(), a.end()), a.end());
    }
    
    int getId(int x) {
        return lower_bound(a.begin(), a.end(), x) - a.begin() + 1;
    }
public:
    vector<int> countSmaller(vector<int>& nums) {
        vector<int> resultList;

        Discretization(nums);

        Init(nums.size() + 1);
        
        for (int i = (int)nums.size() - 1; i >= 0; --i) {
            int id = getId(nums[i]);
            resultList.push_back(Query(id - 1));
            Update(id);
        }

        reverse(resultList.begin(), resultList.end());

        return resultList;
    }
};
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

2、二分查找

同样参考LeetCode-剑指51-数组中的逆序对。我们可以在进行归并排序时，对于左区间中的每一个元素，统计右区间中元素小于它的个数并对应更新即可。其中函数inplace_merge可用于两个有序序列的升序排序。

class Solution {
public:
    using pii = pair<int, int>; // <number, index>
    vector<int> countSmaller(vector<int>& nums) {
        vector<pii> v;
        v.reserve(nums.size());
        
        for (int i = 0; i < nums.size(); ++i) {
            v.emplace_back(nums[i], i);
        }
        
        vector<int> res(v.size());
        merge_sort(v, 0, v.size(), res);
        return res;
    }
    
    void merge_sort(vector<pii>& nums, int lo, int hi, vector<int>& res) {
        if (hi - lo <= 1) return; // 元素个数 <= 1 终止。
        int mid = lo + (hi - lo >> 1);
        merge_sort(nums, lo, mid, res);
        merge_sort(nums, mid, hi, res);
        
        int right = mid;
        
        // 对于左半区间中的每个元素 left，统计右侧比它小的元素的个数
        for (int left = lo; left < mid; ++left) {
            while (right != hi && nums[left] > nums[right]) ++right;
            res[nums[left].second] += right - mid;
        }
        
        inplace_merge(nums.begin() + lo, nums.begin() + mid, nums.begin() + hi);
    }
};
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