493. 翻转对
题目描述
输入整数数组 nums。
若下标 i < j 且 nums[i] > 2 * nums[j]，就称 (i, j) 是一个重要翻转对。
返回数组中重要翻转对的总数。
示例 1
输入：nums = [1,3,2,3,1] 输出：2
解释：下标对 (1,4) 和 (3,4) 满足条件：两个 3 都大于 2 * 1。
示例 2
输入：nums = [2,4,3,5,1] 输出：3
解释：(1,4)、(2,4)、(3,4) 满足条件：4、3、5 都大于 2 * 1。
数据范围
- 数组长度不超过
50000。 - 数组中所有数都在 32 位有符号整数范围内。
解题思路：归并排序
归并分治：把 [lo, hi) 分成左右两半，各自递归计数并排好序。跨越两半的对子里，i 在左半、j 在右半，下标顺序自动满足。由于两半都有序，对左半的 nums[i] 从小到大枚举，右半中满足 nums[i] > 2·nums[j] 的 j 是一段前缀，并且这段前缀只会变长。所以用一个不回退的指针 j 求出前缀长度 j - mid（也可以对每个 i 在右半二分）。计完数再把整段合并排序，交给上一层。
为什么正确
sort(lo, hi) 返回时，nums[lo:hi] 已有序，返回值是这段内部的翻转对数。
复杂度分析
每层双指针 O(n)，共 log n 层；用真正的归并合并时总时间 O(n log n)（本解用库排序合并，是 O(n log² n)），空间 O(n)。
易错点
2 * nums[j] 在 32 位下会溢出，C++/Java 要转成 64 位再乘。先计数再合并，不能把计数条件套在合并的比较上（两者条件不同）。
参考代码
Python、Java、C++、Go、JavaScript、TypeScript 六种语言，逻辑一致。
class Solution:
def reversePairs(self, nums: List[int]) -> int:
def sort(lo, hi):
if hi - lo <= 1:
return 0
mid = (lo + hi) // 2
cnt = sort(lo, mid) + sort(mid, hi)
j = mid
for i in range(lo, mid):
while j < hi and nums[i] > 2 * nums[j]:
j += 1
cnt += j - mid
nums[lo:hi] = sorted(nums[lo:hi])
return cnt
return sort(0, len(nums))class Solution {
private int[] nums;
public int reversePairs(int[] nums) {
this.nums = nums;
return sort(0, nums.length);
}
private int sort(int lo, int hi) {
if (hi - lo <= 1) {
return 0;
}
int mid = (lo + hi) / 2;
int cnt = sort(lo, mid) + sort(mid, hi);
int j = mid;
for (int i = lo; i < mid; i++) {
while (j < hi && (long) nums[i] > 2L * nums[j]) {
j++;
}
cnt += j - mid;
}
Arrays.sort(nums, lo, hi);
return cnt;
}
}class Solution {
public:
int reversePairs(vector<int>& nums) {
function<int(int, int)> sort_ = [&](int lo, int hi) -> int {
if (hi - lo <= 1) {
return 0;
}
int mid = (lo + hi) / 2;
int cnt = sort_(lo, mid) + sort_(mid, hi);
int j = mid;
for (int i = lo; i < mid; i++) {
while (j < hi && (long long)nums[i] > 2LL * nums[j]) {
j++;
}
cnt += j - mid;
}
sort(nums.begin() + lo, nums.begin() + hi);
return cnt;
};
return sort_(0, nums.size());
}
};func reversePairs(nums []int) int {
var sortR func(lo, hi int) int
sortR = func(lo, hi int) int {
if hi-lo <= 1 {
return 0
}
mid := (lo + hi) / 2
cnt := sortR(lo, mid) + sortR(mid, hi)
j := mid
for i := lo; i < mid; i++ {
for j < hi && nums[i] > 2*nums[j] {
j++
}
cnt += j - mid
}
sort.Ints(nums[lo:hi])
return cnt
}
return sortR(0, len(nums))
}var reversePairs = function(nums) {
const sort = (lo, hi) => {
if (hi - lo <= 1) {
return 0;
}
const mid = (lo + hi) >> 1;
let cnt = sort(lo, mid) + sort(mid, hi);
let j = mid;
for (let i = lo; i < mid; i++) {
while (j < hi && nums[i] > 2 * nums[j]) {
j++;
}
cnt += j - mid;
}
const part = nums.slice(lo, hi).sort((a, b) => a - b); for (let t = lo; t < hi; t++) nums[t] = part[t - lo];
return cnt;
};
return sort(0, nums.length);
};function reversePairs(nums: number[]): number {
const sort = (lo: number, hi: number): number => {
if (hi - lo <= 1) {
return 0;
}
const mid = (lo + hi) >> 1;
let cnt = sort(lo, mid) + sort(mid, hi);
let j = mid;
for (let i = lo; i < mid; i++) {
while (j < hi && nums[i] > 2 * nums[j]) {
j++;
}
cnt += j - mid;
}
const part = nums.slice(lo, hi).sort((a, b) => a - b); for (let t = lo; t < hi; t++) nums[t] = part[t - lo];
return cnt;
};
return sort(0, nums.length);
}其他解法
归并排序在合并前用双指针统计跨两半的翻转对，离线分治；树状数组按顺序逐个统计，需要离散化，但思路是在线的。
解法 2：离散化 + 树状数组 时间 O(n log n)，空间 O(n)
把所有 nums[i] 和 2·nums[i] 排序去重，映射成 1~m 的秩。从左到右扫描，树状数组记录已经出现过的数。对当前 x，查询前面不超过 2x 的个数，用已扫描个数减去它，就是前面大于 2x 的个数，累加进答案。然后把 x 插入树状数组。
在线逐个处理，不修改原数组顺序，模板可复用于各种“统计前面比我大/小的数”问题。需要离散化，并注意 2x 超出 32 位整数范围。
class Solution:
def reversePairs(self, nums: List[int]) -> int:
# 离散化：把所有 nums[i] 和 2*nums[i] 映射到 1..m
vals = sorted(set(nums) | {2 * x for x in nums})
rank = {v: i + 1 for i, v in enumerate(vals)}
m = len(vals)
tree = [0] * (m + 1)
def add(i):
while i <= m:
tree[i] += 1
i += i & -i
def query(i): # 已插入的数中秩 <= i 的个数
s = 0
while i > 0:
s += tree[i]
i -= i & -i
return s
ans = 0
for j, x in enumerate(nums):
# 前面 j 个数中大于 2x 的个数
ans += j - query(rank[2 * x])
add(rank[x])
return ansclass Solution {
public int reversePairs(int[] nums) {
int n = nums.length;
long[] all = new long[2 * n];
for (int i = 0; i < n; i++) {
all[2 * i] = nums[i];
all[2 * i + 1] = 2L * nums[i];
}
Arrays.sort(all);
int m = 0;
for (int i = 0; i < all.length; i++) {
if (i == 0 || all[i] != all[i - 1]) all[m++] = all[i];
}
long[] vals = Arrays.copyOf(all, m);
int[] tree = new int[m + 1];
int ans = 0;
for (int j = 0; j < n; j++) {
int s = 0;
for (int i = Arrays.binarySearch(vals, 2L * nums[j]) + 1; i > 0; i -= i & -i) s += tree[i];
ans += j - s;
for (int i = Arrays.binarySearch(vals, (long) nums[j]) + 1; i <= m; i += i & -i) tree[i]++;
}
return ans;
}
}class Solution {
public:
int reversePairs(vector<int>& nums) {
vector<long long> vals;
for (int x : nums) {
vals.push_back(x);
vals.push_back(2LL * x);
}
sort(vals.begin(), vals.end());
vals.erase(unique(vals.begin(), vals.end()), vals.end());
int m = vals.size();
vector<int> tree(m + 1, 0);
auto rank = [&](long long v) { return int(lower_bound(vals.begin(), vals.end(), v) - vals.begin()) + 1; };
int ans = 0;
for (int j = 0; j < (int)nums.size(); j++) {
int s = 0;
for (int i = rank(2LL * nums[j]); i > 0; i -= i & -i) s += tree[i];
ans += j - s;
for (int i = rank(nums[j]); i <= m; i += i & -i) tree[i]++;
}
return ans;
}
};func reversePairs(nums []int) int {
vals := make([]int, 0, 2*len(nums))
for _, x := range nums {
vals = append(vals, x, 2*x)
}
sort.Ints(vals)
m := 0
for i, v := range vals {
if i == 0 || v != vals[i-1] {
vals[m] = v
m++
}
}
vals = vals[:m]
tree := make([]int, m+1)
ans := 0
for j, x := range nums {
s := 0
for i := sort.SearchInts(vals, 2*x) + 1; i > 0; i -= i & -i {
s += tree[i]
}
ans += j - s
for i := sort.SearchInts(vals, x) + 1; i <= m; i += i & -i {
tree[i]++
}
}
return ans
}var reversePairs = function(nums) {
const vals = [...new Set([...nums, ...nums.map(x => 2 * x)])].sort((a, b) => a - b);
const rank = new Map();
vals.forEach((v, i) => rank.set(v, i + 1));
const m = vals.length;
const tree = new Int32Array(m + 1);
let ans = 0;
for (let j = 0; j < nums.length; j++) {
let s = 0;
for (let i = rank.get(2 * nums[j]); i > 0; i -= i & -i) s += tree[i];
ans += j - s;
for (let i = rank.get(nums[j]); i <= m; i += i & -i) tree[i]++;
}
return ans;
};function reversePairs(nums: number[]): number {
const vals = [...new Set([...nums, ...nums.map(x => 2 * x)])].sort((a, b) => a - b);
const rank = new Map<number, number>();
vals.forEach((v, i) => rank.set(v, i + 1));
const m = vals.length;
const tree = new Int32Array(m + 1);
let ans = 0;
for (let j = 0; j < nums.length; j++) {
let s = 0;
for (let i = rank.get(2 * nums[j])!; i > 0; i -= i & -i) s += tree[i];
ans += j - s;
for (let i = rank.get(nums[j])!; i <= m; i += i & -i) tree[i]++;
}
return ans;
}