ধরুন আমাদের একটি অ্যারে সংখ্যা আছে, আমাদের গণনা নামে আরেকটি অ্যারে খুঁজে বের করতে হবে, এই গণনা অ্যারেতে, গণনা [i] সংখ্যার ডানদিকে ছোট উপাদানের সংখ্যা সংরক্ষণ করে।
সুতরাং যদি ইনপুটটি এরকম হয়:[5,2,7,1], তাহলে ফলাফল হবে [2,1,1,0]।
এটি সমাধান করতে, আমরা এই পদক্ষেপগুলি অনুসরণ করব -
-
আপডেট() নামে একটি পদ্ধতি সংজ্ঞায়িত করুন, এটি সূচক, অ্যারে বিট এবং n
নেবে -
যখন ইনডেক্স <=n, do −
-
বিট বাড়ান[সূচী]
-
index =index + (index) AND ( - index)
-
-
query() নামক একটি অ্যারে সংজ্ঞায়িত করুন, এটি সূচক এবং বিট অ্যারে গ্রহণ করবে
-
উত্তর :=0
-
যখন সূচক> 0, −
করুন-
ans =ans + bit[index]
-
সূচক =সূচক – (সূচী এবং - সূচক)
-
-
উত্তর ফেরত দিন
-
-
প্রধান পদ্ধতি থেকে, নিম্নলিখিতগুলি করুন -
-
n :=সংখ্যার আকার
-
n
আকারের একটি অ্যারে রেস-এর সংজ্ঞা দিন -
যদি (n অ-শূন্য) মিথ্যা হয়, তাহলে, রিটার্ন রিটার্ন
-
maxx :=0, minn =সংখ্যা [0]
-
শুরু করার জন্য i :=1, যখন i
-
minn :=nums[i] এবং minn
-
-
শুরু করার জন্য i :=0, যখন i
-
nums[i] :=nums[i] - minn + 1
-
maxx :=সংখ্যার সর্বোচ্চ [i] এবং maxx
-
-
maxx + 1
আকারের একটি অ্যারে বিট সংজ্ঞায়িত করুন -
শুরু করার জন্য i :=n - 1, যখন i>=0, i কমিয়ে 1 do −
-
সংখ্যা =সংখ্যা[i] – 1
-
x :=ফাংশন ক্যোয়ারী কল করুন(num,bit)
-
res[i] :=x
-
ফাংশন আপডেট কল করুন (সংখ্যা + 1, বিট, ম্যাক্সক্স)
-
-
রিটার্ন রিটার্ন
উদাহরণ
আরো ভালোভাবে বোঝার জন্য আসুন নিচের বাস্তবায়ন দেখি -
#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, ]
