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

约 6 分钟
文章信息 11 个分类 7 个标签
分类
LeetCode CodeTop 困难 未解决 10-20 腾讯 字节 华为 滴滴 虾皮 商汤
标签
数组 二分查找 分治 有序集合 线段树 归并排序 树状数组

题目描述

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

image-20260928220613239

image-20260928220613241

题意分析

为原数组的每个下标 i 统计：有多少个 j > i 满足 nums[j] < nums[i]。返回的计数数组必须仍与原下标一一对应，不能按数值排序后输出答案。

“更小”是严格小于，相等值不算；右侧多个相同的小值分别占据不同位置，都要分别计数。最后一个位置右侧为空，计数自然为零。

解法：归并排序统计逆序关系

核心思路

[!blue]

直接为每个位置扫描右侧需要平方时间。把数组按原下标分成左右两段后，左段内和右段内的贡献可以递归求出，剩下只需统计“左段元素与右段更小元素”形成的跨段关系。

为了加速跨段比较，让递归返回的两个子段按数值有序。但不能丢掉答案对应的原位置，所以实际排序的是 indexes 下标数组，比较时读取 nums[indexes[i]]，计数始终写入 counts[原下标]。每个子段包含的原下标范围不变，因此左段所有元素在原数组中都位于右段元素之前。

归并时，用 rightMoved 记录本次合并中已先放入结果的右段元素数量。如果当前右值严格小于当前左值，就先取右值并加一；由于左段也有序，它比当前以及后续尚未处理的左值都小。

当轮到某个左元素输出时，先前取走的 rightMoved 个右元素全部严格更小，而仍未取走的右元素都不小于它，所以这就是该左元素在本次合并中新增的完整贡献。相等时必须先取左侧，避免把相等值记入这个计数；右段耗尽后，剩余左元素也仍需加上累计贡献。

同段关系由递归处理，跨段关系只在它们第一次分属左右两半的那次合并中统计，因此每个合法数对恰好计一次。最后将有序下标复制回当前区间，供上一层继续归并，原 nums 内容无需修改。

解题步骤

  1. 初始化 indexes[i] = i、临时下标数组 temp 和答案数组 counts。
  2. 递归处理半开区间 [left, right)，长度不超过一时直接返回。
  3. 两侧处理完成后，从各自开头归并，并将本轮 rightMoved 初始化为零。
  4. 右侧值严格更小时取右侧并增加计数；否则取左侧，把 rightMoved 加到该元素原下标的答案。某侧耗尽时继续按相同规则处理另一侧。
  5. 将 temp 的当前区间复制回 indexes；全部归并结束后，按原下标返回 counts。

代码实现

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)$。

关键点总结

[!green]

  • 必须排序原下标而不是只排序数值，否则无法把计数写回原位置。
  • rightMoved 只统计已经越过当前左元素的右段元素；它们原本在右侧，且值更小，正好是答案贡献。
  • 相等时先取左段，才能排除相等元素，落实“严格小于”。
  • 这与普通逆序对归并的区别在于：普通题只累加总数，本题要把贡献记到每个左元素的原下标。

易错点总结

[!yellow]

  • 相等时先取右段，会错误地把相等值记作严格更小，必须优先取左段。
  • rightMoved 是一次合并内的局部计数，每次合并都要从零开始，答案数组则累加各层贡献。
  • 只排序数值或只累计全局逆序对总数，都无法恢复每个原下标自己的答案。
  • 右段耗尽后，剩余左元素仍要加上已经移走的右侧数量，不能只复制它们。
  • 合并后要回写有序下标，否则上一层无法利用两侧有序性正确统计。

相似题目

题目 难度 关联与区别
493. 翻转对 困难 同样在归并两个有序半区时计跨区间数对，原题条件为左值大于右值两倍。
327. 区间和的个数 困难 同样利用归并计数消除一层枚举，原题对前缀差的上下界范围计数。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/56290699
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！