数据结构
网络
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 次浏览
广告