C++ में स्वयं के बाद छोटी संख्याओं की गणना

मान लीजिए हमारे पास एक सरणी nums है, हमें एक और सरणी ढूंढनी है जिसे count कहा जाता है, इस count सरणी में, count[i] nums[i] के दाईं ओर छोटे तत्वों की संख्या संग्रहीत करता है।

तो यदि इनपुट है: [5,2,7,1], तो परिणाम [2,1,1,0] होगा।

इसे हल करने के लिए, हम निम्नलिखित चरणों का पालन करेंगे -

• एक विधि update() परिभाषित करें, जो इंडेक्स, सरणी bit और n लेगी

• जब इंडेक्स <= n, करें -

  • bit[इंडेक्स] बढ़ाएं

  • इंडेक्स = इंडेक्स + (इंडेक्स) AND ( - इंडेक्स)

• एक सरणी query() परिभाषित करें, जो इंडेक्स और bits सरणी लेगी

  • ans := 0

  • जब इंडेक्स > 0, करें -

    • ans = ans + bit[इंडेक्स]

    • इंडेक्स = इंडेक्स - (इंडेक्स AND - इंडेक्स)

  • ans लौटाएं

• मुख्य विधि से, निम्नलिखित करें -

• n := nums का आकार

• आकार n की एक सरणी res परिभाषित करें

• यदि (n शून्येतर है) असत्य है, तो, res लौटाएं

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

• i := 1 से आरंभ करें, जब i < n, i को 1 से बढ़ाएं करें -

  • minn := nums[i] और minn का न्यूनतम

• i := 0 से आरंभ करें, जब i < n, i को 1 से बढ़ाएं करें -

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

  • maxx := nums[i] और maxx का अधिकतम

• आकार maxx + 1 की एक सरणी bit परिभाषित करें

• i := n - 1 से आरंभ करें, जब i >= 0, i को 1 से घटाएं करें -

  • num = nums[i] - 1

  • x := फ़ंक्शन query(num,bit) को कॉल करें

  • res[i] := x

  • फ़ंक्शन update(num + 1, bit, maxx) को कॉल करें

• res लौटाएं

उदाहरण

बेहतर समझ के लिए निम्नलिखित कार्यान्वयन देखें -

#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, ]