当前位置：首页 > news >正文

LeetCode算法日记 - Day 27: 计算右侧小于当前元素的个数、翻转对

news 2025/9/1 5:42:38

1. 计算右侧小于当前元素的个数

1.1 题目解析

1.2 解法

1.3 代码实现

2. 翻转对

2.1 题目解析

2.2 解法

2.3 代码实现

1. 计算右侧小于当前元素的个数

315. 计算右侧小于当前元素的个数 - 力扣（LeetCode）

给你一个整数数组 nums ，按要求返回一个新数组 counts 。数组 counts 有该性质： counts[i] 的值是 nums[i] 右侧小于 nums[i] 的元素的数量。

示例 1：

输入：nums = [5,2,6,1]
输出：[2,1,1,0] 
解释：
5 的右侧有 2 个更小的元素 (2 和 1)
2 的右侧仅有 1 个更小的元素 (1)
6 的右侧有 1 个更小的元素 (1)
1 的右侧有 0 个更小的元素

示例 2：

输入：nums = [-1]
输出：[0]

示例 3：

输入：nums = [-1,-1]
输出：[0,0]

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

1.1 题目解析

题目本质：

对每个位置 i，统计它右侧有多少元素 < nums[i]。这是“离线统计 + 有序累积”的典型问题：如果能让“右侧区域”保持有序，那么当一个左侧元素要“落位”时，就能一次性把比它小的右侧元素数目加上去。
常规解法：对每个 i 向右扫一遍计数，或把每个 i 与其右边所有元素比较。
复杂度 O(n²)，n 最多 1e5，超时。
问题分析：O(n²) 不行；要降低到 O(n log n)。要么用“平衡树/树状数组/线段树”边插边查，要么在“归并排序”的有序合并过程中顺手统计。
思路转折：用 归并排序（分治）。关键是不直接搬值，而是搬“原始下标”：
- 比较用 nums[index[*]]；
- 计数写回 counts[index[*]]。
  这样既能用数值排队，又不丢原始位置，统计才能落对人。

1.2 解法

算法思想
维护一个下标数组 index，对下标做归并：

降序归并 + 一次性加法：左右两段都保持降序。若 nums[left] > nums[right]，则右半段从 cur2 到 right 的所有元素都更小，直接 += (right - cur2 + 1) 并把左元素出列；否则先出右元素。

i）初始化：index[i]=i，counts 全 0，准备 tmp 临时数组。

ii）分治：mergeSort(nums, left, right)。

iii）合并：

指针 cur1 =left, cur2 =mid+1，k 写入 tmp。
若 nums[index[cur1]] <= nums[index[cur2]]
tmp[k++]=index[cur2++]。
否则：counts[index[cur1]] += (right - j + 1)
tmp[k++]=index[cur1++]。
扫尾：
while (cur1 <= mid) tmp[k++] = index[cur1++];
while (cur2 <= right) tmp[k++] = index[cur2++];
回写：
for (int j = left; j <= right; j++) index[j] = tmp[j - left];

iiii）返回 counts 的列表形式。

易错点

只搬下标，不搬值：比较写 nums[index[*]]，统计写 counts[index[*]]。
回写的是 index，不是 nums：index[j]=tmp[j-left] 或让 k 从 left 开始写
注意 while 循环里比大小时判断的条件
多层归并要累加：counts[...] += ...，不能覆盖。
tmp 不是答案数组，它只是合并时的 辅助排序区，是归并用的临时缓冲区，帮助我们把当前区间 [left..right] 合并成有序；排序这一步是必须的，因为我们借助“有序”的过程，才能在 O(n log n) 里顺手统计“右边更小”的个数。
counts：是真正的答案数组，counts[cur1] 表示 nums[cur1] 右侧比它小的数量，最后返回它即可。
k++ 只是为了推进左半区的扫描，别忘了这个数组是记录下标而不是原始数组的值，所以要推进下标数组的下标值。
index 数组的作用是“保持数值和原始下标之间的映射关系不丢失”。

1.3 代码实现

import java.util.*;class Solution {int[] index;   // 记录每个元素的“原始下标”，在归并过程中只搬动下标int[] tmp;     // 临时数组，用来辅助归并排序（保存下标，不保存值）int[] counts;  // 结果数组，counts[i] = nums[i] 右侧比它小的数量public List<Integer> countSmaller(int[] nums) {int n = nums.length;tmp = new int[n];counts = new int[n];index = new int[n];// 初始化下标数组，初始时 index[i] = ifor (int i = 0; i < n; i++) {index[i] = i;}// 分治归并排序mergeSort(nums, 0, n - 1);// 把 counts 数组转成 List<Integer> 返回List<Integer> list = new ArrayList<>(n);for (int v : counts) list.add(v);return list;}public void mergeSort(int[] nums, int left, int right) {if (left >= right) return;  // 递归基：区间只有一个元素时结束int mid = left + (right - left) / 2;// 递归排序左半区mergeSort(nums, left, mid);// 递归排序右半区mergeSort(nums, mid + 1, right);int cur1 = left, cur2 = mid + 1, k = 0;// 合并两个有序区间（这里用“降序”方式）while (cur1 <= mid && cur2 <= right) {if (nums[index[cur1]] <= nums[index[cur2]]) {// 如果右边的值更大或相等，先把右边的下标放进 tmptmp[k++] = index[cur2++];} else {// 如果左边的值更大：// 说明右边 [cur2..right] 的元素全都比它小counts[index[cur1]] += (right - cur2 + 1);// 把这个左边元素的下标放进 tmptmp[k++] = index[cur1++];}}// 把左半区剩余元素拷贝进 tmpwhile (cur1 <= mid) tmp[k++] = index[cur1++];// 把右半区剩余元素拷贝进 tmpwhile (cur2 <= right) tmp[k++] = index[cur2++];// 回写：把 tmp 里的结果拷回到 index 数组对应区间for (int j = left; j <= right; j++) {index[j] = tmp[j - left];}}
}

复杂度分析

时间：分治 + 合并为 O(n log n)，每层合并线性。
空间：index/tmp/counts 为 O(n)，递归栈 O(log n)。

2. 翻转对

493. 翻转对 - 力扣（LeetCode）

给定一个数组 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位整数的表示范围内。

2.1 题目解析

题目本质：统计所有满足 i < j 且 nums[i] > 2 * nums[j] 的二元组数量。这是一个“离线统计 + 有序累积”的经典范式：如果左右两段各自有序，就能用双指针线性地数出跨段满足条件的配对数量。
常规解法：双重循环枚举 (i, j)，逐对判断是否 nums[i] > 2*nums[j]。时间复杂度 O(n^2)，n 最多可到 5e4，显然超时。
问题分析：要把复杂度压到 O(n log n)。两条常见路径：
1）平衡树 / 树状数组 / 线段树做“边插边查”；
2）分治归并：在“合并”前用双指针数跨段配对，再做标准归并。
思路转折：采用分治归并。关键点：
- 先数对，后归并：当左右段（[left..mid] 与 [mid+1..right]）各自已升序时，固定左段的 i，右段用 j 单调右移，线性统计满足 nums[i] > 2*nums[j] 的个数。
- 用 long 比较避免溢出：：写成 (long)nums[i] > 2L * (long)nums[j]，不要用 /2.0 的浮点比较。
- 归并阶段使用标准升序合并，保持下一层统计的前提（左右各自升序）。

2.2 解法

算法思想

分治：mergeSort(left, right)。在回溯（合并）前，借助“两侧各自升序”，对每个 i ∈ [left..mid]，移动 j 直到不满足条件为止，累计 j - (mid + 1)。再做一次标准升序归并，保证整体有序供更高层使用。

i）递归到底：left >= right 返回。

ii）递归左右：mergeSort(left, mid) 与 mergeSort(mid+1, right)。

iii）先统计：

j = mid + 1；
对每个 i = left..mid：while (j <= right && (long)nums[i] > 2L * (long)nums[j]) j++;
累加 result += (j - (mid + 1))。

iiii）再归并（升序）：常规双指针把 [left..mid] 与 [mid+1..right] 合并到 tmp，再回写。

iiiii）返回最终 result。

易错点

不要边合并边用 (right - cur2 + 1) 一把加：那是普通逆序对 nums[i] > nums[j] 的套路，对 > 2*nums[j] 不成立。
比较必须用 long：2 * nums[j] 在 int 里可能溢出。
不要用/2.0：浮点精度 + 负数边界容易出错，也不必要。
双计数陷阱：要么用全局 result，要么函数返回值累计，二者不要混用。
合并要升序：保证下一层“先数对”的前提（左右各自已升序）。
指针单调：统计阶段 j 只右移不回退，整体线性。

2.3 代码实现

import java.util.*;class Solution {int[] tmp;int result;public int reversePairs(int[] nums) {tmp = new int[nums.length];mergeSort(nums, 0, nums.length - 1);return result;}// 只做副作用统计与排序，不用返回值累计public void mergeSort(int[] nums, int left, int right){if (left >= right) return;int mid = left + (right - left) / 2;mergeSort(nums, left, mid);mergeSort(nums, mid + 1, right);// 先统计：左右两段各自已升序int j = mid + 1;for (int i = left; i <= mid; i++) {while (j <= right && (long)nums[i] > 2L * (long)nums[j]) j++;// 右半段 [mid+1, j-1] 都满足 nums[i] > 2*nums[?]result += (j - (mid + 1));}// 再归并：标准升序合并int cur1 = left, cur2 = mid + 1, k = 0;while (cur1 <= mid && cur2 <= right) {if (nums[cur1] <= nums[cur2]) {tmp[k++] = nums[cur1++];} else {tmp[k++] = nums[cur2++];}}while (cur1 <= mid)  tmp[k++] = nums[cur1++];while (cur2 <= right) tmp[k++] = nums[cur2++];// 回写for (int t = 0; t < k; t++) {nums[left + t] = tmp[t];}}
}

复杂度分析