leetcode——第315题——树状数组&归并排序 逆序对_leetcode 315

题目：计算右侧小于当前元素的个数

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

/*
使用前缀和的解法，但是需要对原始的数据做一些处理
1、反转后的数组，nums 倒叙反转所得，因为倒叙输入才能转换为前置的 前缀和数组
2、排序后的数组，排序时重复元素归类为同一个，所以排序后的总元素个数是小于等于原始的数组元素个数的
3、频率数组，依次遍历反转后的数组，按照排序数组记录的前后关系，得到前缀和数组
4、前缀和数组，根据频率数组所得，频率数组记录的是频次，
5、最后的输出结果，是倒序的前缀和数组


注意这里的频率数组仅记录次序，因为如果直接使用元素值的话，值会非常大，使内存爆掉   
*/

// 树状数的类原封不动的搬过来
class FenwickTree
{
public:
    // 5、这个忘了写了，构造函数，初始化对象要用的呀，没有构造函数怎么可以的呐~~
    // 注意这里使用 初值列 的方式进行初始化
    FenwickTree (int n) : sums_(n + 1, 0){};

    // 3、定义 update tree
    void update (int i, int val)
    {
        while(i < sums_.size())
        {
            sums_[i] += val;
            i += lowbit(i);
        }
    }

    // 4、定义 query tree
    // 错误之处：没有加const
    int query (int i) const
    {
        int sum = 0;
        while(i > 0)
        {
            sum += sums_[i];
            i -= lowbit(i);
        }
        return sum;
    }

private:
    // 1、定义一个私有成员 用来存储部分和
    vector<int> sums_;
    // 2、定义求 二进制最低有效位 的函数
    // 错误之处：这里写的没加 静态和内联 
    static inline int lowbit(int x)
    {
        return x & (-x);
    }
};

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) 
    {
        // 1、单一不重复元素排序，选用 set 容器，可以直接去重
        set<int> sorted(nums.begin(), nums.end());
        // 2、对排序后的数组，进行序号的标定，存储为一个 哈希映射，key 对应元素值, value是下标也就是大小的次序
        unordered_map<int, int> ranks;
        // 3、很妙的处理，set容器的遍历，用range-for，这里就不能是通过下标来进行遍历访问了
        int rank = 0;
        for(const int num : sorted)
        {
            ranks[num] = ++rank;    // 顺序依次为 1,2,3,4,5... sorted.size()
        }

        vector<int> ans;
        // 4、实例化一个树状数对象，并将树的节点个数初始化为 排序后的数组的个数
        FenwickTree tree(ranks.size()); 
        // 5、倒叙遍历 nums 数组
        for (int i = nums.size() - 1; i >= 0; --i)
        {
            // 先查询树中有多少元素是比目前的值小的，就把它插入结果中
            ans.push_back(tree.query(ranks[nums[i]] - 1)); // 因为树的下标从1开始，所以需要 -1
            // 将这个值早 rank 中的排名在树中更新，也就是前缀和的更新
            tree.update(ranks[nums[i]], 1); //这里的更新也就是做 +1 的操作 
        }

        reverse(ans.begin(), ans.end());
        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
75
76
77
78
79
80
81
82
83
84
85