資料結構
網路
RDBMS
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究C++ 中的反向對
假設我們有一個數組，在這個陣列中，如果滿足以下條件，我們將一對（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）
- 當 first <= high 且 a[first] * 2 < a 時，執行：
- 當 j <= high 時，執行：
- temp[k] := a[j]
- （將 k 加 1）
- （將 j 加 1）
- k := 0
- 從初始化 i := low 開始，當 i <= high 時，更新（將 i 加 1），執行：
- 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
更新於： 2020年6月1日
766 次瀏覽
廣告