您的位置 首页 > 腾讯云社区

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

题目

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

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

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; } }; ---来自腾讯云社区的---ShenduCC

关于作者: 瞎采新闻

这里可以显示个人介绍!这里可以显示个人介绍!

热门文章

留言与评论(共有 0 条评论)
   
验证码: