C++ में सेल्फ के बाद छोटे नंबरों की संख्या

मान लीजिए कि हमारे पास एक सरणी संख्या है, हमें गिनती नामक एक और सरणी ढूंढनी है, इस गिनती सरणी में, गिनती [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, ]