นับจำนวนที่น้อยกว่าหลังจากตนเองใน C++

สมมติว่าเรามีจำนวนอาร์เรย์ เราต้องหาอาร์เรย์อื่นที่เรียกว่า count ในอาร์เรย์การนับนี้ count[i] จะเก็บจำนวนองค์ประกอบที่มีขนาดเล็กลงไว้ทางด้านขวาของ nums[i]

ดังนั้นหากอินพุตเป็นเช่น [5,2,7,1] ผลลัพธ์จะเป็น [2,1,1,0]

เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -

• กำหนดเมธอดหนึ่งที่เรียกว่า update() ซึ่งจะใช้ index, array bit และ n

• ในขณะที่ดัชนี <=n ทำ -

  • เพิ่มบิต[ดัชนี]

  • ดัชนี =ดัชนี + (ดัชนี) และ ( - ดัชนี)

• กำหนดหนึ่งอาร์เรย์ที่เรียกว่า query() ซึ่งจะใช้ดัชนีและบิตอาร์เรย์

  • ตอบ :=0

  • ในขณะที่ดัชนี> 0 ทำ -

    • ans =ans + bit[ดัชนี]

    • ดัชนี =ดัชนี – (ดัชนี AND - ดัชนี)

  • กลับมาอีกครั้ง

• จากวิธีหลัก ให้ทำดังนี้ −

• n :=ขนาดของ nums

• กำหนดขนาดอาร์เรย์ของขนาด n

• ถ้า (n ไม่ใช่ศูนย์) เป็นเท็จ ให้คืนค่า res

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

• สำหรับการเริ่มต้น i :=1 เมื่อ i

  • minn :=นาทีของ nums[i] และ minn

• สำหรับการเริ่มต้น i :=0 เมื่อฉัน

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

  • maxx :=สูงสุดของ nums[i] และ maxx

• กำหนดบิตอาร์เรย์ขนาด maxx + 1

• สำหรับการเริ่มต้น i :=n - 1 เมื่อ i>=0, ลด i โดย 1 ทำ −

  • num =nums[i] – 1

  • x :=เรียกใช้แบบสอบถามฟังก์ชัน (num,bit)

  • res[i] :=x

  • เรียกใช้การอัปเดตฟังก์ชัน (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, ]