C++での自己後の小さい数のカウント

配列numsがあるとすると、countという別の配列を見つける必要があります。このcount配列では、count[i]はnums[i]の右側にある小さい要素の数を格納します。

したがって、入力が[5,2,7,1]の場合、結果は[2,1,1,0]になります。

これを解決するには、次の手順に従います-

• update（）という1つのメソッドを定義します。これには、インデックス、配列ビット、およびn

  が必要です。

• インデックス<=nの場合、実行-

  • ビットを増やす[インデックス]

  • インデックス=インデックス+（インデックス）AND（-インデックス）

• query（）と呼ばれる1つの配列を定義します。これには、インデックスとビット配列が必要です

  • ans：=0

  • インデックス>0の場合、実行-

    • ans =ans+ビット[インデックス]

    • インデックス=インデックス–（インデックスAND-インデックス）

  • ansを返す

• メインの方法から、次のようにします-

• n：=numsのサイズ

• サイズnの配列解像度を定義します

• （nがゼロ以外）がfalseの場合、resを返します

• maxx：=0、minn =nums [0]

• i：=1を初期化するために、i

  • minn：=nums[i]とminnの最小値

• iを初期化する場合：=0、i

  • nums [i]：=nums [i] --minn + 1

  • maxx：=nums[i]とmaxxの最大値

• サイズmaxx+1の配列ビットを定義します

• iを初期化する場合：=n-1、i> =0の場合、iを1つ減らしますdo-

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