【LeetCode315】-计算右侧小于当前元素的个数

方法一(归并)

实现思想

分析
如果使用暴力求解的方式，需要每一个元素从左到右一次遍历统计自己右侧比自己小的个数，时间复杂度为O（n^2）
但其实在这个过程中有些比较时冗余的，以5，8，3为例，3比8小被计数，那么在统计8的时候8明显比5大，且3又在8的右侧也要被计数，但是相当于多比较了一回。概括来说，满足在右侧的条件下，一个数比该数小，肯定也比大于该数的数小。
归并思想
【刷题基础知识】-归并排序

套用归并的框架，主要修改归并代码不修改排序的代码；

i记录左侧数组遍历下标
j记录右侧数组遍历下标（j其实就能代表右侧有多少个元素小于左侧当前值）
count值记录右侧小于当前元素的个数
额外需要记录下元素初始的下标值

核心点

1. 左侧数组和右侧数组合并
   1）左侧数组小于等于右侧数组元素，压入左侧元素，同时更新count+=j值
   2）左侧数组大于右侧数组元素，压入右侧元素，同时更新j=j+1

思考

• Q：归并排序时，明明改变了元素的位置，为什么还会得到正确结果？

• A：归并的时候，划分为两部分，两部分在总体上在原数组中的左右侧属性是不被改变的，例：5,4,2,8，在进行5,4排序归并后，变成了4,5但在总体上，4,5相对于2,8还是在左侧

• Q :为什么这种做法效率更高，高在哪儿里

• A :排序后我们其实也得到了结果，归并排序的时间复杂度为O（nlogn）
  效率更高的本质原因减少了不必要的遍历和比较。
  将左边数组和右边数组进行归并排序时，左边及右边数组都排好序了，在进行合并时，有一个元素来记录右边有多少个元素小于左边当前元素，右侧数组中小于左侧数组当前元素时，其实也说明右侧数组也一定小于左侧数组当前元素后续元素，记住左侧数组中元素是升序排序的。

具体计算过程，如下图所示：

实现代码

class Solution {

private:
    map<int,int> loc;
public:
    //差排序后的数组
    void mergesort_two_vec(vector<pair<int,int>> &re,vector<pair<int,int>> &sec1,vector<pair<int,int>> &sec2,vector<int> &count){
        int i=0,j=0;
        while(i<sec1.size()&&j<sec2.size()){
            if(sec1[i].first<=sec2[j].first){
                count[sec1[i].second]+=j;
                re.push_back(sec1[i]);
                i++;
            }
            else{
                re.push_back(sec2[j]);
                j++;
            }
        }
        while(i<sec1.size()){
            count[sec1[i].second]+=j;
            re.push_back(sec1[i]);
            i++;
        }
        while(j<sec2.size()){
            re.push_back(sec2[j]);
            j++;
        }
    }
    void mergesort(vector<pair<int,int>> &nums,vector<int> &count){
        if(nums.size()<2) return;
        int mid=nums.size()/2;
        vector<pair<int,int>> sec1,sec2;
        for(int i=0;i<mid;i++){
            sec1.push_back(nums[i]);
        }
        for(int i=mid;i<nums.size();i++){
            sec2.push_back(nums[i]);
        }
        mergesort(sec1,count);
        mergesort(sec2,count);
        nums.clear();
        mergesort_two_vec(nums,sec1,sec2,count);
    }
    vector<int> countSmaller(vector<int>& nums) {
        int n=nums.size();
        vector<int> count(n,0);
        vector<pair<int,int>> vec;
        for(int i=0;i<n;i++){
            vec.push_back(make_pair(nums[i],i));
        }
        mergesort(vec,count);
        return count;
    }
};
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

提交结果及分析

时间复杂度O（nlogn）

方法二（二分查找树）

二叉查找树的时间复杂度为O（nlog（n））
思路概括为：
原题是看后面有多少个小于当前节点的，其实可以反过来看，当前已经有多少节点小于当前结点了

为了实现O（nlog（n））的时间复杂度，尝试在构建二分查找树的时候计算出所要结果

每个节点需要多维护一个值就是其左子树的个数

实现代码

struct Node{
    int val;
    int cnt;
    Node* left,*right;
    Node(int val):val(val),cnt(0),left(NULL),right(NULL){;}
};
class Solution {
public:
    void build(Node* root,Node *a,int &cnt_sum){
        if(a->val<=root->val){
            root->cnt++;
            if(!root->left){
                root->left=a;
            }else{
                build(root->left,a,cnt_sum);
            }
        }
        else{
            cnt_sum+=root->cnt+1;
            if(!root->right){
                root->right=a;
            }else{
                build(root->right,a,cnt_sum);
            }
        }
    }
    vector<int> countSmaller(vector<int>& nums) {
        vector<Node*> data;
        for(int i=nums.size()-1;i>=0;i--){
            data.push_back(new Node(nums[i]));
        }
        vector<int> cnt;
        vector<int> re;
        cnt.push_back(0);
        for(int i=1;i<data.size();i++){
            int cnt_sum=0;
            build(data[0],data[i],cnt_sum);
            cnt.push_back(cnt_sum);
        }
        for(int i=data.size()-1;i>=0;i--){
            delete data[i];
            re.push_back(cnt[i]);
        }
        return re;
    }
};
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

提交结果

总结

如果想将O（n^2）的算法转换为O（nlog（n））的算法，一定要找符合O（nlog（n））的数据结构或算法

可能还是归并的要好一些

注意new的空间记得释放