在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, ]