LeetCode 315. 计算右侧小于当前元素的个数
目录
题目描述
题意分析
给一个整数数组
nums，对每个下标i求出counts[i]：满足j > i且nums[j] < nums[i]的下标j的个数。返回和原数组等长的答案数组。要什么：每个位置都要一个答案，不是一个总和。这一点和「逆序对总数」那类题不同，后者只要一个数字，本题要求把贡献落到每个下标上，所以统计过程必须能定位到具体位置。
严格小于是硬性的：
nums[j] == nums[i]不计入。相等值的处理是本题最常见的错误来源。约束信号：
1 <= nums.length <= 10^5，-10^4 <= nums[i] <= 10^4。10^5直接否掉了 $O(n^2)$ 的双重循环（约 $10^{10}$ 次比较，必然超时），要求达到 $O(n \log n)$。值域是[-10^4, 10^4]，含负数、且左右都有界——负数意味着不能拿值直接当数组下标，有界则暗示可以做值域压缩或直接开桶。边界要想到：数组含大量重复值；全是负数；
n = 1时答案是[0]；数组本身已经升序时答案全 0，降序时答案是n-1, n-2, …, 0。
解法：归并排序统计逆序关系
核心思路
暴力枚举每个位置右侧的元素需要 $O(n^2)$。这类“左边元素与右边元素形成多少逆序关系”的问题，可以在归并排序合并两个有序段时一次统计。
排序过程中不直接搬运数值，而是搬运原下标
indexes，这样计数能写回对应答案。合并左右有序段时维护rightMoved，表示已经放入临时数组的右段元素个数：
- 若右段值更小，先放右段元素，并令
rightMoved++。- 若放左段元素，此前移走的右段元素都位于它的原始右侧，且都严格小于它，因此给该左段元素的答案加上
rightMoved。相等时必须先放左段元素，因为题目只统计“严格小于”。归并完成后，当前区间按值有序，计数也已完整覆盖左半段与右半段之间的所有逆序关系；递归则负责各自区间内部的关系。
解题步骤
- 初始化
indexes[i] = i、临时数组temp和计数数组counts。- 递归排序半开区间
[left, right)；长度不超过 1 时返回。- 合并时比较
nums[indexes[i]]与nums[indexes[j]]。右侧更小时先放右侧并增加rightMoved；否则先放左侧，并把rightMoved加到该原下标的计数中。- 将合并后的下标序列复制回
indexes，保证上一层看到的是有序区间。- 把
counts转为题目要求的结果类型。以
[5, 2, 6, 1]为例：合并[5]与[2]时，2 先移走，5 的计数加 1；合并[6]与[1]时，6 的计数加 1。最终合并有序段[2, 5]与[1, 6]，1 先移走，2 和 5 的计数各再加 1，得到[2, 1, 1, 0]。
代码实现
import java.util.ArrayList;
import java.util.List;
class Solution {
public List<Integer> countSmaller(int[] nums) {
int n = nums.length;
int[] indexes = new int[n];
int[] temp = new int[n];
int[] counts = new int[n];
for (int i = 0; i < n; i++) {
indexes[i] = i;
}
mergeSort(nums, indexes, temp, counts, 0, n);
List<Integer> answer = new ArrayList<>(n);
for (int count : counts) {
answer.add(count);
}
return answer;
}
private void mergeSort(int[] nums, int[] indexes, int[] temp,
int[] counts, int left, int right) {
if (right - left <= 1) {
return;
}
int mid = left + (right - left) / 2;
mergeSort(nums, indexes, temp, counts, left, mid);
mergeSort(nums, indexes, temp, counts, mid, right);
int i = left;
int j = mid;
int rightMoved = 0;
for (int k = left; k < right; k++) {
if (j == right ||
(i < mid && nums[indexes[i]] <= nums[indexes[j]])) {
counts[indexes[i]] += rightMoved;
temp[k] = indexes[i++];
} else {
temp[k] = indexes[j++];
rightMoved++;
}
}
for (int k = left; k < right; k++) {
indexes[k] = temp[k];
}
}
}
func countSmaller(nums []int) []int {
n := len(nums)
indexes := make([]int, n)
temp := make([]int, n)
counts := make([]int, n)
for i := range indexes {
indexes[i] = i
}
mergeCount(nums, indexes, temp, counts, 0, n)
return counts
}
func mergeCount(nums, indexes, temp, counts []int, left, right int) {
if right-left <= 1 {
return
}
mid := left + (right-left)/2
mergeCount(nums, indexes, temp, counts, left, mid)
mergeCount(nums, indexes, temp, counts, mid, right)
i, j, rightMoved := left, mid, 0
for k := left; k < right; k++ {
if j == right || (i < mid && nums[indexes[i]] <= nums[indexes[j]]) {
counts[indexes[i]] += rightMoved
temp[k] = indexes[i]
i++
} else {
temp[k] = indexes[j]
j++
rightMoved++
}
}
copy(indexes[left:right], temp[left:right])
}
复杂度分析
- 时间复杂度：$O(n \log n)$。归并排序有 $O(\log n)$ 层，每层合并全部
n个下标。- 空间复杂度：$O(n)$。下标数组、临时数组和答案数组占线性空间，递归栈为 $O(\log n)$。
关键点总结
- 必须排序原下标而不是只排序数值，否则无法把计数写回原位置。
rightMoved只统计已经越过当前左元素的右段元素；它们原本在右侧，且值更小，正好是答案贡献。- 相等时先取左段，才能排除相等元素，落实“严格小于”。
- 这与普通逆序对归并的区别在于：普通题只累加总数，本题要把贡献记到每个左元素的原下标。
- 树状数组加坐标压缩也是 $O(n \log n)$ 解法；归并法不依赖值域，更适合从逆序对模型直接推导。
易错点总结
- 相等时先取右段：
[1, 1]会把右边相等的 1 错算为更小，得到[1, 0]。- 只累加跨段总数：能求出整个数组的逆序对数，却无法回答每个下标各有多少个。
- 排序数值而不携带原下标：排序后失去答案与原位置的对应关系。
- 合并后忘记复制回
indexes：上一层拿到的子区间并未有序，后续计数失效。- 给右段元素增加计数：题目统计的是当前元素右侧更小的数量，贡献应记在被越过的左段元素上。
相似题目
| 题目 | 难度 | 考察点 |
|---|---|---|
| 307. 区域和检索 - 数组可修改 | 中等 | 树状数组单点改 + 区间查的裸题 |
| 327. 区间和的个数 | 困难 | 前缀和上的区间计数 |
| 493. 翻转对 | 困难 | 带系数的跨段比较 |
| 剑指 Offer 51. 数组中的逆序对 | 困难 | 只求逆序对总数，不落到每个下标 |
| 补充题 8. 计算数组的小和 | 中等 | 逆序对统计的加权求和变形 |
| 面试题-最小交换次数（任意交换与相邻交换） | 困难 | 逆序对数即相邻交换的最少次数 |