当前位置:   article > 正文

【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的空间记得释放

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/我家自动化/article/detail/87132
推荐阅读
相关标签
  

闽ICP备14008679号