【小白爬Leetcode315】4.6 计算右侧小于当前元素的个数 Count of Smaller Numbers After Self_归并排序 计算左侧小于当前元素的个数

Leetcode 315 $hard$
点击进入原题链接：Leetcode 315 计算右侧小于当前元素的个数 Count of Smaller Numbers After Self

题目

Discription

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

中文解释

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

思路：归并排序+pair绑定原序数

• 归并排序：
  归并排序（Merge Sort）是建立在归并操作上的一种有效，稳定的排序算法，该算法是采用分治法（Divide and Conquer）的一个非常典型的应用。它是将已有子序列一直二分，直到只剩一个元素，然后合并子序列（合并的过程中排序），直到最后的得到一个排序后的数组，有关时间复杂度和详细解释可以看这篇博文：
  归并排序时间复杂度过程分析
• 本题思路：
  这道题的本意不在于排序，也不需要返回排序后的数组，但是在归并排序的过程中可以解决这道逆序数的问题。
  图片来源：小象学院
  这张图说的不是很好懂，其实就是：j是后半个数组中第j个元素，同时也代表了比前半个数组中第i个元素小的元素个数，由于后半个数组元素在nums数组里肯定是排在前半个数组的后面的，因此j就代表着当前的逆序数。
  通过不断地归并两个各自正序的子序列，我们通过累加j就可以得到最终每个元素对于整个序列而言的逆序数。
  
  但是这里有一个问题：
  归并排序过后的元素的顺序和nums数组不一样了，而题目要求的逆序数数组counts数组是按照nums数组的顺序的，因此我们需要给每个nums数组的元素加上一个序号，形成一个pair，这样在修改counts数组的时候，根据 pair.second（也就是该元素在nums里的原序号）来索引，就不会混乱了。

class Solution {
public:
    vector<int> countSmaller(vector<int>& nums) { // 主函数，用于初始化，调用功能函数，返回结果
        vector<pair<int,int>> vec;
        int len = nums.size();
        vector<int> counts(len,0);
        for(int i=0;i<len;i++){  //绑定元素和该元素在原数组nums的位置
            vec.push_back(make_pair(nums[i],i));
        }
        merge_sort(vec,counts);
        return counts;
    }
private:
    void merge_two_sorted_list(vector<pair<int,int>>& vec,vector<pair<int,int>>& vec1,
    vector<pair<int,int>>& vec2,vector<int>& counts){ // 最核心的部分，合并两个自序列的同时修改counts数组
        int i = 0; // for vec1
        int j = 0; // for vec2
        int len_vec1 = vec1.size();
        int len_vec2 = vec2.size();
        while(i<len_vec1 && j<len_vec2){ // 根据每个元素的大小合并vec1\vec2到vec里
            if(vec1[i].first <= vec2[j].first){
                counts[vec1[i].second] += j; //插前半段元素的时候要注意对counts数组的更新
                vec.push_back(vec1[i]); //把元素插入到新的vec函数里
                i++;
            }
            else{
                vec.push_back(vec2[j]);
                j++;
            }
        }
        //handle the rest of vec1 and vec2(if exist)
        for(;i<len_vec1;i++){
            counts[vec1[i].second] += j; //插前半段元素的时候要注意对counts数组的更新
            vec.push_back(vec1[i]);
        }
        for(;j<len_vec2;j++){
            vec.push_back(vec2[j]);
        }
    
    }
    void merge_sort(vector<pair<int,int>>& vec,vector<int>& counts){ //递归归并排序函数，用于对原来数组进行二分
        int len = vec.size();
        if(len<2){ //二分到只有一个元素就return，回溯到上一级
            return;
        }
        vector<pair<int,int>> vec1;
        vector<pair<int,int>> vec2;
        //二分vec到vec1和vec2
        int mid = len/2;
        for(int i=0;i<mid;i++){
            vec1.push_back(vec[i]);
        }
        for(int i=mid;i<len;i++){
            vec2.push_back(vec[i]);
        }
        merge_sort(vec1,counts); //继续二分左半个数组
        merge_sort(vec2,counts); //继续二分右半个数组
        vec.clear(); //清空vec，以便容纳合并后的vec
        merge_two_sorted_list(vec,vec1,vec2,counts);
    }
};
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

思路二 搜索二叉树 Binary Search Tree

【小白爬Leetcode315】6.4 （搜索二叉树版）计算右侧小于当前元素的个数 Count of Smaller Numbers After Self