专栏首页算法修养LeetCode 315. Count of Smaller Numbers After Self(线段树,树状数组)

LeetCode 315. Count of Smaller Numbers After Self(线段树,树状数组)

题目

题意:找到数组里每个元素的右边有多少个元素小于当前元素

题解:单点更新,区间查询。线段树或者树状数组都可以。注意要离散化

class Solution {
public:
    int c[100005];
    int n;
    map<int,int> m;
    vector<int> countSmaller(vector<int>& nums) {
        
        vector<int> a = nums;
        sort(a.begin(),a.end());
        for(int i=0;i<a.size();i++)
        {
            m[a[i]]=i+1;
        }
        n=nums.size();
        vector<int> ans;
        
        for(int i=n-1;i>=0;i--)
        {
            ans.push_back(sum(m[nums[i]]-1));
            update(m[nums[i]]);
        }
        
        reverse(ans.begin(),ans.end());
        return ans;
            
    }
    
    int lowbit(int x)
    {
        return x&(-x);
    }
    
    void update(int pos)
    {
        while(pos<=n)
        {
            c[pos]++;
            pos+=lowbit(pos);
        }
    }
    
    int sum(int pos)
    {
        int ans=0;
        while(pos>0)
        {
            ans+=c[pos];
            pos-=lowbit(pos);
        }
        return ans;
    }
};

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • LeetCode 32. Longest Valid Parentheses

    ShenduCC
  • pta 习题集5-18 打印学生选课清单

    假设全校有最多40000名学生和最多2500门课程。现给出每门课的选课学生名单,要求输出每个前来查询的学生的选课清单。 输入格式: 输入的第一行是两个正整...

    ShenduCC
  • LeetCode 89 Gray Code

    当然也有通项公式,用位运算写起来,也巨简单,虽然不知道为什么:Gray[n] = n^(n>>1)

    ShenduCC
  • 853. Car Fleet

    思路 把车按离终点的距离从远到近排列。 车队的到达时间取决于排在最前面的那辆车。 从远到近遍历车辆,如果上一辆车到达终点的时间比这一辆车快,就合并把上一辆...

    平凡的学生族
  • Q67 Add Binary

    Given two binary strings, return their sum (also a binary string). For example, ...

    echobingo
  • 【CCF】最小差值

    版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。 ...

    喜欢ctrl的cxk
  • hdu----(1257)最少拦截系统(dp/LIS)

    最少拦截系统 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Ja...

    Gxjun
  • E.Sequence in the Pocket

    用户2965768
  • 洛谷P2572 [SCOI2010]序列操作(ODT)

    attack
  • 【POJ 1679】The Unique MST(次小生成树)

    找出最小生成树,同时用Max[i][j]记录i到j的唯一路径上最大边权。然后用不在最小生成树里的边i-j来替换,看看是否差值为0。

    饶文津

扫码关注云+社区

领取腾讯云代金券