C++ में रिवर्स पेयर्स (Reverse Pairs)

मान लीजिए हमारे पास एक ऐरे है, इस ऐरे में हम एक जोड़ी (A[i] और A[j]) को महत्वपूर्ण रिवर्स पेयर कहेंगे यदि यह निम्न शर्त को संतुष्ट करता है -

• यदि i < j और A[i] > 2 * nums[j]

हमें महत्वपूर्ण रिवर्स पेयर्स की संख्या ज्ञात करनी है। तो यदि इनपुट [2,8,7,7,2] जैसा है, तो परिणाम 3 होगा।

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

• ans := 0
• एक फंक्शन merge() परिभाषित करें, यह एक ऐरे a, low, mid, high लेगा,
• k := high - low + 1
• आकार k का एक ऐरे temp परिभाषित करें
• i := low, j = mid + 1, k := 0
• first := mid + 1
• जब i <= mid, करें -
  • जब first <= high और a[first] * 2 < a, करें -
    • (first को 1 से बढ़ाएं)
  • जब (j <= high और a[j] <= a[i]), करें -
    • temp[k] := a[j]
    • (j को 1 से बढ़ाएं)
    • (k को 1 से बढ़ाएं)
  • ans := ans + first - (mid + 1)
  • temp[k] := a[i]
  • (i को 1 से बढ़ाएं)
  • (k को 1 से बढ़ाएं)
• जब j <= high, करें -
  • temp[k] := a[j]
  • (k को 1 से बढ़ाएं)
  • (j को 1 से बढ़ाएं)
• k := 0
• i := low से प्रारंभ करें, जब i <= high, i बढ़ाते हुए, करें -
  • a[i] := temp[k]
  • (k को 1 से बढ़ाएं)
• एक फंक्शन calc() परिभाषित करें, यह एक ऐरे a, low, high लेगा,
• यदि low >= high, तो -
  • वापस करें
• mid := low + (high - low)/2
• calc(a, low, mid) फंक्शन कॉल करें
• calc(a, mid + 1, high) फंक्शन कॉल करें
• merge(a, low, mid, high) फंक्शन कॉल करें
• एक फंक्शन solve() परिभाषित करें, यह एक ऐरे A लेगा,
• ans := 0
• n := A का आकार
• calc(A, 0, n - 1) फंक्शन कॉल करें
• ans वापस करें
• मुख्य विधि से, निम्न करें
• solve(nums) फंक्शन कॉल वापस करें

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

उदाहरण

#include <bits/stdc++.h> using namespace std; typedef long long int lli; class Solution { public:    int ans = 0;    void merge(vector <int> &a, lli low, lli mid, lli high){       lli k = high - low + 1;       vector <lli> temp(k);       lli i = low, j = mid + 1;       k = 0;       lli first = mid + 1;       while(i <= mid){          while(first <= high && (lli)a[first] * 2 < (lli)a[i]) {             first++;          }          while(j <= high && a[j] <= a[i])          {             temp[k] = a[j];             j++;             k++;          }          ans += first - (mid + 1);          temp[k] = a[i];          i++;          k++;       }       while(j <= high){          temp[k] = a[j];          k++;          j++;       }       k = 0;       for(lli i = low; i <= high; i++){          a[i] = temp[k];          k++;       }    }    void calc(vector <int> &a, lli low, lli high){       if(low >= high)return;       lli mid = low + (high - low)/2;       calc(a, low, mid);       calc(a, mid + 1, high);       merge(a, low, mid, high);    }    lli solve(vector<int> &A) {       ans = 0;       lli n = A.size();       calc(A, 0, n - 1);       return ans;    }    int reversePairs(vector<int>& nums) {       return solve(nums);    } }; main(){    Solution ob;    vector<int> v = {2,8,7,7,2};    cout << (ob.reversePairs(v)); }

इनपुट

{2,8,7,7,2}

आउटपुट

3