Computer >> Máy Tính >  >> Lập trình >> C ++

Các cặp đảo ngược trong C ++

Giả sử chúng ta có một mảng, trong mảng này chúng ta sẽ nói một cặp (A [i] và A [j]) là các cặp đảo ngược quan trọng nếu điều này thỏa mãn điều kiện sau -

  • nếu tôi 2 * nums [j]

Chúng ta phải tìm ra số lượng các cặp đảo ngược quan trọng. Vì vậy, nếu đầu vào là [2,8,7,7,2], thì kết quả sẽ là 3.

Để giải quyết vấn đề này, chúng tôi sẽ làm theo các bước sau -

  • ans:=0
  • Xác định một hàm merge (), điều này sẽ lấy một mảng a, low, mid, high,
  • k:=high - low + 1
  • Xác định nhiệt độ mảng có kích thước k
  • i:=low, j =mid + 1, k:=0
  • đầu tiên:=mid + 1
  • while i <=mid, do -
    • while đầu tiên <=high và a [first] * 2
    • (tăng trước 1)
  • while (j <=high and a [j] <=a [i]), do -
    • temp [k]:=a [j]
    • (tăng j lên 1)
    • (tăng k thêm 1)
  • ans:=ans + first - (mid + 1)
  • temp [k]:=a [i]
  • (tăng tôi lên 1)
  • (tăng k thêm 1)
  • while j <=high, do -
    • temp [k]:=a [j]
    • (tăng k thêm 1)
    • (tăng j lên 1)
  • k:=0
  • để khởi tạo i:=low, khi i <=high, cập nhật (tăng i lên 1), thực hiện -
    • a [i]:=temp [k]
    • (tăng k thêm 1)
  • Xác định một hàm calc (), hàm này sẽ nhận một mảng a, low, high,
  • nếu thấp> =cao, thì -
    • trở lại
  • giữa:=low + (cao - thấp) / 2
  • gọi hàm calc (a, low, mid)
  • gọi hàm calc (a, mid + 1, high)
  • gọi hàm hợp nhất (a, low, mid, high)
  • Xác định một hàm giải quyết (), điều này sẽ nhận một mảng A,
  • ans:=0
  • n:=kích thước của A
  • gọi hàm calc (A, 0, n - 1)
  • trả lại ans
  • Từ phương pháp chính, hãy thực hiện như sau
  • trả về gọi hàm giải quyết (nums)
  • Hãy cùng chúng tôi xem cách triển khai sau để hiểu rõ hơn -

    Ví dụ

    #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));
    }

    Đầu vào

    {2,8,7,7,2}

    Đầu ra

    3