Luobuyu's Blog

0%

315.计算右侧小于当前元素的个数

发表于 分类于 ， ， 热度： ℃ 评论：
本文字数： 4.2k 阅读时长 ≈ 4 分钟
类似逆序对问题，需要使用归并排序，也可以使用树状数组解决。

315.计算右侧小于当前元素的个数

题目描述：

给出一个长度为 $n$ 的整数数组nums，按要求返回一个新数组counts。其中 counts[i]的值表示nums[i]右侧小于nums[i]的元素数量。

数据范围：
$1\le n \le 10^5;-10^4\le nums[i]\le 10^4$

题解：

可以使用类似归并排序的二分操作，也可以直接使用线段树或者树状数组维护 $[1,max\_val]$ ，直接查询比当前值小的元素的个数，即前缀和 $[1,val-1]$ 。

由于数据有负的，可以使用离散化，使用 $unordered\_map$ 或者 $sort+unique+lower\_bound$ ，也可以不使用离散化，直接全都加上一个数，将负的转化为正的。

归并排序做法：

归并排序可以用来求逆序对有关的问题，明显也是逆序对，但是只是一边的逆序对。假设分成了 $[l, mid], [mid+1, right]$ 且两边都是有序的，令 $i = l,j=mid + 1$ 。

如果 $a[i] \le a[j]$ 那么说明这次该拿 $a[i]$ 放入 $tmp$ 数组了， $a[j]$ 前面的已经全放入 $tmp$ 数组了，因此存在 $j - 1 - mid - 1 + 1 = j - mid - 1$ 个比 $a[i]$ 小的元素，更新答案。注意当右侧为空时，说明右侧的全部元素都比 $a[i]$ 小，记得更新答案。

从另一个角度，如果 $a[i] > a[j]$ ，那么说明这次应该拿 $a[j]$ 了， $a[j]$ 比 $a[i]$ 以及后面的都小，因此对后面的元素都要贡献答案。但是这时需要遍历 $a[i]$ 后面的元素，因此不适合。如果是求逆序对，那么就可以直接加上 $mid - i + 1$ 。而且当右侧为空的时候也不用继续更新答案了，因为贡献前面已经加上了。

代码：

unordered_map离散化

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    struct Tree
    {
        vector<int> c;
        int max_size;
        Tree(int n) : c(n + 1), max_size(n) {}
        int lowbit(int x) { return x & -x; }
        void add(int index, int value)
        {
            while (index <= max_size)
            {
                c[index] += value;
                index += lowbit(index);
            }
        }
        int query(int index)
        {
            int ans = 0;
            while (index >= 1)
            {
                ans += c[index];
                index -= lowbit(index);
            }
            return ans;
        }
    };

    unordered_map<int, int> mp;
    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> nums_b = nums;
        sort(nums_b.begin(), nums_b.end());
        int tmp = 0;
        for (int i = 0; i < n; ++i)
        {
            if (!mp.count(nums_b[i]))
                mp[nums_b[i]] = ++tmp;
        }
        int max_size = mp[nums_b[n - 1]];
        Tree tree(max_size);
        vector<int> ret(n, 0);
        for (int i = n - 1; i >= 0; --i)
        {
            ret[i] = tree.query(mp[nums[i]] - 1);
            tree.add(mp[nums[i]], 1);
        }
        return ret;
    }
};

sort + unique + lower_bound离散化

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    struct Tree
    {
        vector<int> c;
        int max_size;
        Tree(int n) : c(n + 1), max_size(n) {}
        int lowbit(int x) { return x & -x; }
        void add(int index, int value)
        {
            while (index <= max_size)
            {
                c[index] += value;
                index += lowbit(index);
            }
        }
        int query(int index)
        {
            int ans = 0;
            while (index >= 1)
            {
                ans += c[index];
                index -= lowbit(index);
            }
            return ans;
        }
    };

    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        vector<int> nums_b = nums;
        nums_b.emplace_back(-1e4 - 1);
        sort(nums_b.begin(), nums_b.end());
        int max_size = unique(nums_b.begin(), nums_b.end()) - nums_b.begin();
        for (int i = 0; i < n; ++i)
        {
            nums[i] = lower_bound(nums_b.begin(), nums_b.begin() + max_size, nums[i]) - nums_b.begin();
        }

        Tree tree(max_size);
        vector<int> ret(n, 0);
        for (int i = n - 1; i >= 0; --i)
        {
            ret[i] = tree.query(nums[i] - 1);
            tree.add(nums[i], 1);
        }
        return ret;
    }
};

归并排序逆序对做法

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
class Solution
{
public:
    const static int maxn = 1e5 + 10;
    const static int maxm = 1e5 + 10;
    const static int INF = 0x3f3f3f3f;
    vector<pair<int, int>> tmp; // value, index
    vector<pair<int, int>> nums_p;
    void mix_merge(vector<int> &ans, vector<pair<int, int>> &nums, int l, int mid, int r)
    {
        // [l, mid], [mid + 1, r]
        int l1 = l, l2 = mid + 1, l3 = l;
        while (l1 <= mid && l2 <= r)
        {
            if (nums[l1].first <= nums[l2].first)
            {
                ans[nums[l1].second] += l2 - mid - 1;
                tmp[l3++] = nums[l1++];
            }
            else
            {
                tmp[l3++] = nums[l2++];
            }
        }
        while (l1 <= mid)
        {
            ans[nums[l1].second] += l2 - mid - 1;
            tmp[l3++] = nums[l1++];
        }
        while (l2 <= r)
            tmp[l3++] = nums[l2++];
        for (int i = l; i <= r; ++i)
        {
            nums[i] = tmp[i];
        }
    }

    void merge_sort(vector<int> &ans, vector<pair<int, int>> &nums, int l, int r)
    {
        if (l == r)
            return;
        int mid = (l + r) >> 1;
        merge_sort(ans, nums, l, mid);
        merge_sort(ans, nums, mid + 1, r);
        mix_merge(ans, nums, l, mid, r);
    }

    vector<int> countSmaller(vector<int> &nums)
    {
        int n = nums.size();
        tmp.resize(n);
        nums_p.resize(n);
        for (int i = 0; i < n; ++i)
        {
            nums_p[i] = {nums[i], i};
        }
        vector<int> ans(n);
        merge_sort(ans, nums_p, 0, n - 1);
        return ans;
    }
};