C++ में रिवर्स पेयर

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

• अगर मैं 2* अंक[j]

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

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

• उत्तर:=0
• एक फ़ंक्शन मर्ज () को परिभाषित करें, यह एक सरणी लेगा, निम्न, मध्य, उच्च,
• k :=उच्च - निम्न + 1
• के आकार की एक सरणी अस्थायी परिभाषित करें
• i :=कम, j =मध्य + 1, k :=0
• पहला :=मध्य + 1
• जबकि मैं <=बीच में, −
  . करें
  • जबकि पहले <=उच्च और एक [पहले] * 2 <ए, करते हैं −
    • (पहले 1 से बढ़ाएं)
  • जबकि (j <=उच्च और a[j] <=a[i]), करते हैं −
    • अस्थायी[k] :=a[j]
    • (j को 1 से बढ़ाएं)
    • (k 1 से बढ़ाएं)
  • उत्तर:=उत्तर + प्रथम - (मध्य + 1)
  • अस्थायी[k] :=a[i]
  • (मैं 1 से बढ़ाएँ)
  • (k 1 से बढ़ाएं)
• जबकि j <=उच्च, करें −
  • अस्थायी[k] :=a[j]
  • (k 1 से बढ़ाएं)
  • (j को 1 से बढ़ाएं)
• k :=0
• इनिशियलाइज़ करने के लिए i :=Low, जब i <=high, अपडेट करें (i को 1 से बढ़ाएँ), −
  करें
  • a[i] :=temp[k]
  • (k 1 से बढ़ाएं)
• एक फ़ंक्शन कैल्क () को परिभाषित करें, यह एक, निम्न, उच्च, एक सरणी लेगा,
• यदि निम्न>=उच्च, तो −
  • वापसी
• मध्य :=निम्न + (उच्च-निम्न)/2
• फ़ंक्शन कैल्क (ए, लो, मिड) को कॉल करें
• फ़ंक्शन को कॉल करें कैल्क (ए, मिड + 1, हाई)
• फ़ंक्शन मर्ज को कॉल करें (ए, लो, मिड, हाई)
• एक फ़ंक्शन को हल करें परिभाषित करें (), यह एक सरणी A लेगा,
• उत्तर:=0
• n :=A का आकार
• फ़ंक्शन को कॉल करें कैल्क(ए, 0, एन -1)
• वापसी उत्तर
• मुख्य विधि से, निम्न कार्य करें
• रिटर्न कॉल फंक्शन सॉल्व (अंक)

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

उदाहरण

#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