一道逆序对的变体题目,稍作改变即可解决。
给定一个数组 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位整数的表示范围内。
在归并排序的过程中利用两个数组均为有序的特性,用两个指针分别指向 ${\rm mid}$ 和 ${\rm r}$ 处并不断向左移动,过程中即可统计翻转对。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
| class Solution {
#define COUT(x) #x << "->" << (x) << " "
public:
int cnt;
int reversePairs(vector<int>& nums) {
int n = nums.size();
if(!n) return 0;
vector<int> helper(n);
cnt = 0;
mergeSort(nums, helper, 0, n - 1);
return cnt;
}
void mergeSort(vector<int> &a, vector<int> &b, int l, int r) {
if(l == r) return;
int mid = (l + r) / 2;
mergeSort(a, b, l, mid);
mergeSort(a, b, mid + 1, r);
for(int i = mid, j = r; i >= l && j >= mid + 1; i--) {
bool flag = false;
while(j >= mid + 1) {
if((long long)a[i] > 2LL * a[j]) {
flag = true;
break;
}
j--;
}
if(flag) {
cnt += (j - mid);
}
}
int i = l, j = mid + 1;
for(int k = l; k <= r; k++) {
if(j > r || i <= mid && a[i] <= a[j]) {
b[k] = a[i++];
} else {
b[k] = a[j++];
}
}
for(int k = l; k <= r; k++)
a[k] = b[k];
}
};
|
与通常的树状数组维护逆序对不同,这里需要维护的是 ${\rm nums}[i]$ 与 $2\cdot{\rm nums}[j]$ 的关系,因此需要做如下变动:
记 $n={\rm nums.size()}$,先将 ${ { {\rm nums}[i],,2\cdot{\rm nums}[i];;|;;0 \leq i < n } }$ 离散化,记为 $m$;之后以 $[1..2n]$ 初始化树状数组;
此时,对每个 $j;(0 \leq j < n)$,我们试图统计 ${\rm nums}[j]$ 左侧大于 $2 \cdot {\rm nums}[j]$ 的数目。因此我们正向扫描 ${\rm nums}$,并在过程中对于每个 $j$:
- 计算 ${\rm ask}(2n) - {\rm ask}(m[2 \cdot {\rm nums}[j]])$,这是 ${\rm nums}[j]$ 之前被扫描过的,大于 $2 \cdot {\rm nums}[j]$ 的数目;
- ${\rm add}(m[{\rm nums}[j]], 1)$。
这样一边扫描一边更新,即可得出所有翻转对个数。
另外,由于离散化需要排序,树状数组做法的常数比归并排序大。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
#define COUT(x) #x << "->" << (x) << " "
public:
struct BinTree {
vector<int> c;
int n;
BinTree(int _size): n(_size) {
c.resize(_size + 1);
}
static constexpr int lowbit(int x) {
return (x & (-x));
}
int ask(int x) {
int ans = 0;
for( ; x; x -= lowbit(x))
ans += c[x];
return ans;
}
void add(int x, int y) {
for( ; x <= n; x += lowbit(x))
c[x] += y;
}
};
int reversePairs(vector<int>& nums) {
int n = (int)nums.size();
set<long long> s;
for(int i = 0; i < n; i++) {
s.insert(nums[i]);
s.insert(2LL * nums[i]);
}
unordered_map<long long, int> m;
int cnt = 0;
for(auto &it : s) {
m.insert(make_pair(it, ++cnt));
}
BinTree t(cnt);
int ans = 0;
for(int i = 0; i < n; i++) {
int right = t.ask(cnt);
int left = t.ask(m[2LL * nums[i]]);
ans += right - left;
t.add(m[nums[i]], 1);
}
return ans;
}
};
|