题目描述
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:
Input: [5,2,6,1]
Output: [2,1,1,0]
Explanation:
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.
题意:给一个无序数组,统计每个位置上后面有多少个数字小于自己。
算法1
(线段树) $O(nlogn)$
题解1:树状数组/线段树。我们首先将数组元素离散化到1-N
之间,这时候我们使用数组A[k]
代表当前第k
小的元素出现了多少次,tree
是关于A[i]
的树状数组。我们从后遍历每一个元素,如果当前元素是第k
小的,那么我们可以求和A[1:k - 1]
代表的就是后面比当前元素小的元素个数,然后将A[k] ++
。树状数组可以在$O(logn)$的时间复杂度内完成上述的区间求和和单点更新操作,所以总的时间复杂度为$O(nlogn)$。
C++ 代码
class Solution {
public:
int n;
vector<int> tree;
inline int lowbit(int x) {return x & -x;}
void update(int idx,int delta)
{
while(idx <= n)
{
tree[idx] += delta;
idx += lowbit(idx);
}
}
int getSum(int idx)
{
int res = 0;
while(idx > 0)
{
res += tree[idx];
idx -= lowbit(idx);
}
return res;
}
vector<int> countSmaller(vector<int>& nums) {
int m = nums.size();
vector<int> res(m,0);
vector<int> temp = nums;
// 排序去除重复元素
sort(temp.begin(),temp.end());
temp.erase(unique(temp.begin(), temp.end()), temp.end());
n = temp.size();
unordered_map<int,int> hash;
tree = vector<int>(n + 1,0);
// 将数组元素离散化处理,下标从1开始范围为[1,n],为了和树状数组对应。
for(int i = 0; i < n ; i ++)
hash[temp[i]] = i + 1;
for(int i = m - 1;i >= 0; i --)
{
res[i] = getSum(hash[nums[i]] - 1);
update(hash[nums[i]],1);
}
return res;
}
};