在C ++中自我后的小数计数
假设我们有一个nums数组，我们必须找到另一个名为count的数组，在此count数组中，count[i]存储位于nums[i]右侧的较小元素的数量。
因此，如果输入类似于：[5,2,7,1]，则结果将为[2,1,1,0]。
为了解决这个问题，我们将遵循以下步骤-
定义一个称为的方法update()，它将采用索引，数组位和n
当索引<=n时，执行-
增加位[索引]
索引=索引+（索引）AND（-索引）
定义一个名为的数组query()，它将采用index和bits数组
ANS=ANS+位[索引]
索引=索引–（索引AND-索引）
回答：=0
当索引>0时，执行-
返回ans
从主要方法中，执行以下操作-
n：=nums的大小
定义大小为n的数组res
如果（n为非零）为false，则返回res
maxx：=0，minn=nums[0]
用于初始化i：=1，当i<n时，将i加1做-
minn：=nums[i]和minn的最小值
用于初始化i：=0，当i<n时，将i增加1做-
nums[i]：=nums[i]-minn+1
maxx：=nums[i]和maxx的最大值
定义大小为maxx+1的数组位
用于初始化i：=n-1，当i>=0时，将i减1做-
num=nums[i]–1
x：=调用函数query(num,bit)
res[i]：=x
调用函数update（num+1，bit，maxx）
返回资源
示例
让我们看下面的实现以更好地理解-
#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, ]