C++ 中 Self 之后较小数字的计数
假设我们有一个数组 nums，我们必须找到另一个名为 count 的数组，在这个 count 数组中，count[i] 存储了 nums[i] 右侧较小元素的数量。
因此，如果输入如下:[5,2,7,1]，则结果将是 [2,1,1,0]。
为了解决这个问题，我们将遵循以下步骤 −
定义一个名为 update() 的方法，它将采用索引、数组位和 n
当 index <= n 时，执行 −
increase bit[index]
index = index + (index) AND ( - index)
定义一个名为 query() 的数组，它将采用索引和位数组
ans := 0
while index > 0, do −
ans = ans + bit[index]
index = index – (index AND - index)
return ans
从 main 方法中，执行以下操作 −
n := size of nums
定义一个大小为 n 的数组 res
如果 (n 非零) 为假，则返回 res
maxx := 0, minn = nums [0]
初始化 i := 1，当 i < n 时，将 i 增加 1 执行 −
minn := min of nums[i] and minn
初始化 i := 0，当 i < n 时，将 i 增加 1 执行 −
nums[i] := nums[i] - minn + 1
maxx := max of nums[i] and maxx
定义一个大小为 maxx + 1 的数组 bit
初始化 i := n - 1，当 i >= 0 时，将 i 减 1 执行 −
num = nums[i] – 1
x := 调用函数 query(num,bit)
res[i] := x
调用函数 update(num + 1, bit, maxx)
return res
示例
让我们看看下面的实现以便更好地理解 −
#include <bits/stdc++.h>
using namespace std;
void print_vector(vector<auto> v){
cout << "[";
for(int i = 0; i<v.size(); i++){
cout << v[i] << ", ";
}
cout << "]"<<endl;
}
class Solution {
public:
void update(int index,vector <int>& bit, int n){
while(index<=n){
bit[index]++;
index += (index)&(-index);
}
}
int query(int index, vector <int> bit){
int ans = 0;
while(index>0){
ans+=bit[index];
index -= index&(-index);
}
return ans;
}
vector<int> countSmaller(vector<int>& nums) {
int n = nums.size();
vector <int> res(n);
if(!n)return res;
int maxx = 0;
int minn = nums[0];
for(int i =1;i<n;i++)minn = min(nums[i],minn);
for(int i =0;i<n;i++){
nums[i] = nums[i]-minn+1;
maxx = max(nums[i],maxx);
}
vector <int> bit(maxx+1);
for(int i =n-1;i>=0;i--){
int num = nums[i]-1;
int x = query(num,bit);
res[i] = x;
update(num+1,bit,maxx);
}
return res;
}
};
main(){
Solution ob;
vector<int> v = {5,2,7,1};
print_vector(ob.countSmaller(v));
}
输入
[5,2,7,1]
输出
[2, 1, 1, 0, ]
