C++에서 Self 뒤에 있는 더 작은 숫자의 개수

배열 nums가 있다고 가정하고 count라는 다른 배열을 찾아야 합니다. 이 count 배열에서 count[i]는 nums[i] 오른쪽에 더 작은 요소의 수를 저장합니다.

따라서 입력이 [5,2,7,1]과 같으면 결과는 [2,1,1,0]이 됩니다.

이 문제를 해결하기 위해 다음 단계를 따릅니다. −

• update()라는 메서드를 하나 정의하면 인덱스, 배열 비트 및 n

  이 사용됩니다.

• 동안 인덱스 <=n, 수행 -

  • 비트 증가[색인]

  • 인덱스 =인덱스 + (인덱스) AND ( - 인덱스)

• query()라는 하나의 배열을 정의하면 인덱스와 비트 배열이 필요합니다.

  • 답변 :=0

  • 인덱스> 0인 동안 수행 -

    • ans =ans + 비트[색인]

    • 인덱스 =인덱스 – (인덱스 AND - 인덱스)

  • 반환

• 기본 방법에서 다음을 수행하십시오 -

• n :=숫자 크기

• 크기가 n인 배열 res를 정의

• (n이 0이 아님) 거짓이면 res를 반환합니다.

• maxx :=0, minn =숫자 [0]

• i를 초기화하기 위해 :=1, i

  • minn :=nums[i] 및 minn의 최소값

• i를 초기화하기 위해 :=0, i

  • nums[i] :=nums[i] - 최소값 + 1

  • maxx :=nums[i] 및 maxx의 최대값

• maxx + 1

  크기의 배열 비트 정의

• i를 초기화하기 위해 :=n - 1, i>=0일 때 i를 1만큼 감소 do -

  • 숫자 =숫자[i] – 1

  • x :=함수 호출 query(num,bit)

  • 해상도[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, ]