假设我们有一个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, ]