leetcode315. 计算右侧小于当前元素的个数/归并排序_leetcode 315 mergesort

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

给定一个整数数组 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 个更小的元素.
1
2
3
4
5
6
7

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/count-of-smaller-numbers-after-self
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

基本思想1：暴力

遍历数组，直接借助一个临时存储空间来存储遍历过的元素，并使得临时存储空间中的元素有序存放。

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        if(nums.size() == 0)
            return {};
        vector<int> counts(nums.size(), 0);
        vector<int> help;
        help.push_back(nums.back());
        for(int i = nums.size() - 2; i >= 0; --i){
            auto pos = lower_bound(help.begin(), help.end(), nums[i]);
            counts[i] = pos - help.begin();
            help.insert(pos, nums[i]);
        }
        return counts;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

基本思想2：归并排序

这道题有点像计算逆序数。
核心思想：

• 归并的时候计算右边有几个元素比当前元素小
• 只需在将左边的元素取出的时候进行计算，其值为右边已经遍历过的元素的个数

多说一点：

• 直接借助下标便可计算右边小于该元素的个数
• 结果是求的每个元素右边有几个元素小于它，需要借助一个下标数组来记录元素的位置

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) {
        //归并计算逆序对
        if(nums.size() == 0)
            return {};
        vector<int> index;
        for(int i = 0; i < nums.size(); ++i)
            index.push_back(i);
        vector<int> temp(nums.size());
        vector<int> counts(nums.size(), 0);
        merge_sort(nums, index, temp, 0, nums.size() - 1, counts);
        return counts;
    }
    void merge_sort(vector<int>& nums, vector<int> &index, vector<int> &temp, int left, int right, vector<int> &counts){
        if(left == right)
            return;
        int mid = (left + right) >> 1;
        cout << mid << endl;
        merge_sort(nums, index, temp, left, mid, counts);
        merge_sort(nums, index, temp, mid + 1, right, counts);
        int i = left, j = mid + 1;
        int k = left;
        temp = index;
        while(i <= mid && j <= right){
            if(nums[temp[i]] <= nums[temp[j]]){
                index[k++] = temp[i];
                counts[temp[i]] += j - (mid + 1);
                ++i;
                
            }
            else{
                index[k++] = temp[j];
                ++j;
            }            
        }
        while(i <= mid){
            index[k++] = temp[i];
            counts[temp[i]] += j - (mid + 1);
            ++i;
        }
        while(j <= right){
            index[k++] = temp[j];
            ++j;
        }
        
    }
};
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