Đếm các số nhỏ hơn sau tự trong C ++

Giả sử chúng ta có một mảng num, chúng ta phải tìm một mảng khác gọi là count, trong mảng count này, count [i] lưu trữ số phần tử nhỏ hơn ở bên phải nums [i].

Vì vậy, nếu đầu vào là:[5,2,7,1], thì kết quả sẽ là [2,1,1,0].

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

• Xác định một phương thức được gọi là update (), phương thức này sẽ lấy chỉ mục, mảng bit và n

• trong khi chỉ mục <=n, do -

  • tăng bit [chỉ số]

  • index =index + (index) AND (- index)

• Xác định một mảng được gọi là query (), mảng này sẽ lấy chỉ mục và mảng bit

  • ans:=0

  • trong khi chỉ mục> 0, do -

    • ans =ans + bit [chỉ mục]

    • index =index - (index AND - index)

  • trả lại ans

• Từ phương thức chính, thực hiện như sau -

• n:=kích thước của nums

• Xác định res mảng có kích thước n

• nếu (n khác 0) là false, thì trả về res

• maxx:=0, minn =nums [0]

• để khởi tạo i:=1, khi i

  • minn:=min of nums [i] and minn

• để khởi tạo i:=0, khi i

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

  • maxx:=max of nums [i] và maxx

• Xác định một bit mảng có kích thước maxx + 1

• để khởi tạo i:=n - 1, khi i> =0, giảm i đi 1 do -

  • num =nums [i] - 1

  • x:=Gọi truy vấn hàm (num, bit)

  • res [i]:=x

  • Gọi cập nhật chức năng (num + 1, bit, maxx)

• trả lại res

Ví dụ

Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

#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));
}

Đầu vào

[5,2,7,1]

Đầu ra

[2, 1, 1, 0, ]