मान लीजिए कि हमारे पास एक सरणी संख्या है, हमें गिनती नामक एक और सरणी ढूंढनी है, इस गिनती सरणी में, गिनती [i] संख्याओं के दाईं ओर छोटे तत्वों की संख्या को संग्रहीत करती है [i]।
तो अगर इनपुट इस तरह है:[5,2,7,1], तो परिणाम [2,1,10] होगा।
इसे हल करने के लिए, हम इन चरणों का पालन करेंगे -
-
अद्यतन () नामक एक विधि को परिभाषित करें, यह अनुक्रमणिका, सरणी बिट और n लेगा
-
जबकि अनुक्रमणिका <=n, करें -
-
बिट बढ़ाएँ[सूचकांक]
-
अनुक्रमणिका =अनुक्रमणिका + (सूचकांक) और (- अनुक्रमणिका)
-
-
क्वेरी () नामक एक सरणी को परिभाषित करें, यह अनुक्रमणिका और बिट्स सरणी लेगा
-
उत्तर:=0
-
जबकि अनुक्रमणिका> 0, करें -
-
उत्तर =उत्तर + बिट [सूचकांक]
-
अनुक्रमणिका =अनुक्रमणिका - (सूचकांक और - अनुक्रमणिका)
-
-
वापसी उत्तर
-
-
मुख्य विधि से, निम्न कार्य करें -
-
n :=अंकों का आकार
-
n आकार की एक सरणी रेस परिभाषित करें
-
अगर (n गैर-शून्य है) गलत है, तो, वापसी फिर से करें
-
अधिकतम:=0, मिनट =अंक [0]
-
i :=1 को इनिशियलाइज़ करने के लिए, जब i
-
minn :=min of nums[i] and minn
-
-
प्रारंभ करने के लिए i :=0, जब i
-
अंक [i] :=अंक[i] - minn + 1
-
अधिकतम:=अधिकतम अंक[i] और अधिकतम
-
-
अधिकतम + 1
आकार के सरणी बिट को परिभाषित करें -
प्रारंभ करने के लिए i :=n-1, जब i>=0, i को 1 से घटाएं -
-
अंक =अंक [i] - 1
-
x:=फ़ंक्शन क्वेरी को कॉल करें (संख्या, बिट)
-
रेस [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, ]
