0493. Reverse Pairs
===================
题目信息
--------
:题号: 0493
:难度: Hard
:主题: 下标对、严格两倍关系、负数、数量统计
:原题: `LeetCode 0493 `_
:重点: 必须满足 ``i < j``、条件是 ``nums[i] > 2 * nums[j]``、严格大于、乘二比较可能超出 32 位
题目重述
--------
给定整数数组 ``nums``,统计重要逆序对的数量。重要逆序对是满足以下两个条件的下标对 ``(i, j)``:
.. code-block:: text
i < j
nums[i] > 2 * nums[j]
``nums.length`` 位于 ``[1, 5 * 10^4]``,元素在 32 位有符号整数范围内。不同下标对分别计数;比较是严格大于,等于两倍时不算。输入可能含负数,计算 ``2 * nums[j]`` 时不能因 32 位溢出改变比较结果。
自建示例
--------
一个前项与两个后项配对:
.. code-block:: text
输入:nums = [5,1,2]
输出:2
解释:下标对 (0,1) 满足 5 > 2×1,(0,2) 满足 5 > 2×2;其余下标对不满足。
负数也可能形成重要逆序对:
.. code-block:: text
输入:nums = [-5,-5]
输出:1
解释:唯一的下标对满足 -5 > 2×(-5) = -10,因此应计数。
归并排序中跨左右半段计数
------------------------
归并排序把数组分成两个已排序半段。统计跨越中点的逆序对时,对每个左半段元素 ``nums[i]``,用右半段指针找出所有满足 ``nums[i] > 2 * nums[j]`` 的位置;左右半段都已排序,所以右指针只向前移动,不需要为每个 ``i`` 重新扫描。
比较 ``2 * nums[j]`` 时显式提升到 ``long long``,避免负数和 32 位边界造成溢出。统计完成后再按普通归并合并两半,供上层继续使用。
C++ 实现
--------
.. code-block:: cpp
class Solution {
long long mergeSort(std::vector& nums, int left, int right,
std::vector& buffer) {
if (left >= right) return 0;
int middle = left + (right - left) / 2;
long long answer = mergeSort(nums, left, middle, buffer) +
mergeSort(nums, middle + 1, right, buffer);
int j = middle + 1;
for (int i = left; i <= middle; ++i) {
while (j <= right &&
static_cast(nums[i]) >
2LL * nums[j]) {
++j;
}
answer += j - (middle + 1);
}
int i = left;
j = middle + 1;
int write = left;
while (i <= middle && j <= right) {
if (nums[i] <= nums[j]) {
buffer[write++] = nums[i++];
} else {
buffer[write++] = nums[j++];
}
}
while (i <= middle) buffer[write++] = nums[i++];
while (j <= right) buffer[write++] = nums[j++];
for (int index = left; index <= right; ++index) {
nums[index] = buffer[index];
}
return answer;
}
public:
int reversePairs(std::vector& nums) {
if (nums.empty()) return 0;
std::vector buffer(nums.size());
return static_cast(mergeSort(
nums, 0, static_cast(nums.size()) - 1, buffer));
}
};
代码分析
--------
右指针单调前进的前提是左右半段已经分别有序;合并时恢复整体有序,递归层层保持这个前提。每层合并和计数均为线性,时间复杂度为 ``O(n log n)``,辅助数组和递归栈空间为 ``O(n)``。