首页 > 代码库 > 315. Count of Smaller Numbers After Self
315. Count of Smaller Numbers After Self
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]
.
Example:
Given nums = [5, 2, 6, 1] To the right of 5 there are 2 smaller elements (2 and 1). To the right of 2 there is only 1 smaller element (1). To the right of 6 there is 1 smaller element (1). To the right of 1 there is 0 smaller element.
Return the array [2, 1, 1, 0]
.
解题思路:求逆序数对,可以用线段树或者后缀数组求解。由于数值可能为负数,所以需要离散化或者加上最小的数+1。
离散化:
#define lowbit(i) (i&(-i)) const int maxn = 100010; struct node{ int val,pos; }temp[maxn]; bool cmp(node a,node b){ return a.val<b.val; } class Solution { public: int c[maxn]={0}; int A[maxn]={0}; void update(int x,int v){ for(int i=x;i<maxn;i+=lowbit(i)){ c[i]+=v; } } int getSum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)){ sum+=c[i]; } return sum; } vector<int> countSmaller(vector<int>& nums) { vector<int>ans; int n=nums.size(); for(int i=0;i<n;i++){ temp[i].pos=i; temp[i].val=nums[i]; } sort(temp,temp+n,cmp); for(int i=0;i<n;i++){ if(i==0||temp[i].val!=temp[i-1].val){ A[temp[i].pos]=i+1; } else A[temp[i].pos]= A[temp[i-1].pos]; } for(int i=n-1;i>=0;i--){ update(A[i],1); ans.push_back(getSum(A[i]-1)); } reverse(ans.begin(),ans.end()); return ans; } };
最小数+1:
#define lowbit(i) (i&(-i)) const int maxn = 100010; class Solution { public: int c[maxn]={0}; void update(int x,int v){ for(int i=x;i<maxn;i+=lowbit(i)){ c[i]+=v; } } int getSum(int x){ int sum=0; for(int i=x;i>0;i-=lowbit(i)){ sum+=c[i]; } return sum; } vector<int> countSmaller(vector<int>& nums) { vector<int>ans; int n=nums.size(),mmin=INT_MAX; for(int i=0;i<n;i++){ mmin=min(mmin,nums[i]); } for(int i=0;i<n;i++){ nums[i]=nums[i]-mmin+1; } for(int i=n-1;i>=0;i--){ update(nums[i],1); ans.push_back(getSum(nums[i]-1)); } reverse(ans.begin(),ans.end()); return ans; } };
315. Count of Smaller Numbers After Self
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。