C++でのリバースペア

配列があると仮定します。この配列では、次の条件を満たす場合、1つのペア（A[i]とA[j]）を重要な逆ペアと呼びます-

• if i 2 * nums [j]

重要なリバースペアの数を見つける必要があります。したがって、入力が[2,8,7,7,2]の場合、結果は3になります。

これを解決するには、次の手順に従います-

• ans：=0
• 関数merge（）を定義します。これにより、配列a、low、mid、highが取得されます。
• k：=高-低+ 1
• サイズkのアレイ温度を定義します
• i：=低、j =中+1、k：=0
• 最初：=半ば+ 1
• i <=midの間、-
  を実行します
  • 最初の<=が高く、a[最初の]* 2 を実行します。
  • （最初に1ずつ増やします）
• while（j <=high and a [j] <=a [i]）、do −
  • temp [k]：=a [j]
  • （jを1増やします）
  • （kを1増やします）
• ans：=ans + first-（mid + 1）
• temp [k]：=a [i]
• （iを1増やします）
• （kを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