# 翻转对
给定一个数组 nums ，如果 i < j 且 nums[i] > 2*nums[j] 我们就将 (i, j) 称作一个重要翻转对。
你需要返回给定数组中的重要翻转对的数量。
示例 1:
输入: [1,3,2,3,1]
输出: 2
示例 2:
输入: [2,4,3,5,1]
输出: 3
注意:
- 给定数组的长度不会超过
50000。
- 输入数组中的所有数字都在32位整数的表示范围内。
以下错误的选项是？
## aop
### before
```cpp
#include
using namespace std;
```
### after
```cpp
int main()
{
Solution sol;
int res;
vector nums = {1, 3, 2, 3, 1};
res = sol.reversePairs(nums);
cout << res;
return 0;
}
```
## 答案
```cpp
class Solution
{
public:
int lowbit(int x)
{
return (int)x & x;
}
int getSum(int x, vector &c)
{
int sum = 0;
for (int i = x; i > 0; i -= lowbit(i))
{
sum += c[i];
}
return sum;
}
void update(vector &c, int x, int v)
{
for (int i = x; i < c.size(); i += lowbit(i))
{
c[i] += v;
}
}
int reversePairs(vector &nums)
{
int maxN = (INT_MAX) / 2, minN = (INT_MIN) / 2;
set ss;
for (auto t : nums)
{
ss.insert(t);
if (t <= maxN && t >= minN)
ss.insert(t * 2);
}
unordered_map m;
int n = ss.size();
auto it = ss.begin();
for (int i = 1; i <= n; i++)
{
m[*it] = i;
it++;
}
vector sum(n + 1, 0);
int res = 0;
for (auto t : nums)
{
if (t < minN)
res += getSum(n, sum);
else if (t < maxN)
{
int idx = m[2 * t];
res += (getSum(n, sum) - getSum(idx, sum));
}
update(sum, m[t], 1);
}
return res;
}
};
```
## 选项
### A
```cpp
class Solution
{
public:
int cnt = 0;
vector tmp;
void merge(vector &nums, int beg, int mid, int end)
{
int i = beg, j = mid + 1;
int k = 0;
while (i <= mid && j <= end)
{
if (nums[i] <= nums[j])
tmp[k++] = nums[i++];
else
tmp[k++] = nums[j++];
}
while (i <= mid)
tmp[k++] = nums[i++];
while (j <= end)
tmp[k++] = nums[j++];
copy(tmp.begin(), tmp.begin() + k, nums.begin() + beg);
}
void merge_sort(vector &nums, int beg, int end)
{
if (beg >= end)
return;
int mid = beg + (end - beg) / 2;
merge_sort(nums, beg, mid);
merge_sort(nums, mid + 1, end);
int i = beg, j = mid + 1;
while (j <= end)
{
while (i <= mid && long(nums[i]) <= 2 * long(nums[j]))
++i;
cnt += mid - i + 1;
++j;
}
if (nums[mid] <= nums[mid + 1])
return;
merge(nums, beg, mid, end);
}
int reversePairs(vector &nums)
{
int n = nums.size();
tmp = vector(n);
merge_sort(nums, 0, n - 1);
return cnt;
}
};
```
### B
```cpp
class Solution
{
public:
int mergeSort(vector &nums, int l, int r)
{
if (l >= r)
return 0;
int res = 0, mid = (l + r) / 2;
res += mergeSort(nums, l, mid);
res += mergeSort(nums, mid + 1, r);
int tl = l, tm = mid, tr = mid + 1;
while (tl <= mid && tr <= r)
{
if ((long)nums[tl] > 2 * (long)nums[tr])
{
res += mid - tl + 1;
++tr;
}
else
{
++tl;
}
}
vector tmp(r - l + 1);
int i = l, j = mid + 1, k = 0;
while (i <= mid && j <= r)
{
if (nums[i] <= nums[j])
{
tmp[k++] = nums[i++];
}
else
tmp[k++] = nums[j++];
}
while (i <= mid)
tmp[k++] = nums[i++];
while (j <= r)
tmp[k++] = nums[j++];
for (int i = l; i <= r; i++)
{
nums[i] = tmp[i - l];
}
return res;
}
int reversePairs(vector &nums)
{
return mergeSort(nums, 0, nums.size() - 1);
}
};
```
### C
```cpp
class Solution
{
public:
int cnt = 0;
int reversePairs(vector &nums)
{
int n = nums.size();
for (int i = 0; i < n - 1; ++i)
{
for (int j = i + 1; j < n; ++j)
{
if (long(nums[i]) > 2 * long(nums[j]))
++cnt;
}
}
return cnt;
}
};
```