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 đầu tiên <=high và a [first] * 2
- 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)
- temp [k]:=a [j]
- (tăng k thêm 1)
- (tăng j lên 1)
- a [i]:=temp [k]
- (tăng k thêm 1)
- trở lại
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