参考文献
ref{:target=”_blank”}
使用树状数组优化,将time复杂度从O(n^2)降低到O(nlgn)
对于每个数求比其小的数,从右向左遍历,每个数占用一个id并add 1,则计算的前缀和就是右端比其小的数
这里采用加上一个offset将数字置于 [1, 2N]内,也可以使用 排序-》去重-》lower_bound下标 来离散化
C++ 代码
class Solution {
public:
const int N{20010};
vector<int> tree_;
int lowbit(int n){
return n&-n;
}
void add(int id, int c){
for(int i=id; i<=N; i+=lowbit(i))tree_[i] += c;
}
int query(int id){
int res = 0;
for(int i=id; i>0; i-=lowbit(i))res += tree_[i];
return res;
}
vector<int> countSmaller(vector<int>& nums) {
tree_.resize(N);
int n = nums.size();
vector<int> res(n);
const int offset = 1e4+5;
for(int i=n-1; i>=0; i--){
int x = nums[i] + offset;
res[i] = query(x-1);
add(x, 1);
}
return res;
}
};
离散化栗子
class Solution {
public:
int n_;
vector<int> tree_;
int lowbit(int n){
return n&-n;
}
void add(int id, int c){
for(int i=id; i<=n_; i+=lowbit(i))tree_[i] += c;
}
int query(int id){
int res = 0;
for(int i=id; i>0; i-=lowbit(i))res += tree_[i];
return res;
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
// 离散化
vector<int> nums_id(nums);
sort(nums_id.begin(), nums_id.end());
// 去重后取排序id做映射
n_ = unique(nums_id.begin(), nums_id.end()) - nums_id.begin();
nums_id.resize(n_);
tree_.resize(n_+1);
for(int i=0; i<n; ++i){
// 下标从1开始
nums[i] = lower_bound(nums_id.begin(), nums_id.end(), nums[i]) - nums_id.begin() + 1;
}
vector<int> res(n);
for(int i=n-1; i>=0; i--){
int x = nums[i];
res[i] = query(x-1);
add(x, 1);
}
return res;
}
};