LeetCode 1122. 数组的相对排序

约 4 分钟
文章信息 6 个分类 4 个标签
分类
LeetCode CodeTop 简单 未解决 1-2 华为
标签
数组 哈希表 排序 计数排序

题目描述

✅ 1122. 数组的相对排序

image-20260929070937435

题意分析

重排 arr1：凡是也出现在 arr2 中的值，都按 arr2 给定的先后顺序成组放在前面；没有出现在 arr2 中的值，统一放在后面并按数值升序排列。

arr1 可以包含重复值，必须保留每个值的全部出现次数。题目中 arr2 的值互不相同且都来自 arr1，元素范围为 0 到 1000，因此可以直接用固定值域的计数表组织输出，无需自定义比较排序。

解法：计数排序

核心思路

[!blue]

先完整扫描 arr1，令 count[v] 记录值 v 出现了多少次。统计结束后，原数组的所有信息都已保存在计数表中，可以安全地将 arr1 本身作为结果区，从下标零重新写入。

第一阶段按 arr2 的顺序处理每个值，把它的全部副本连续写出。每写入一次就将 count[v] 减一，直到归零再处理下一个值，保证相对优先顺序正确且同值集中出现。

第二阶段从 0 到 1000 扫描计数表，把尚未消耗的次数依次写出。第一阶段已经处理的值计数为零，不会再次输出；还剩的值都是不在 arr2 中的元素，按下标递增扫描就自然满足尾部升序要求。

每次写入都恰好消耗一次原始出现，两个阶段合起来消耗全部计数，因此不会丢掉重复值，也不会多写元素。结果位置总共前进 arr1.length 次，不需要改变数组长度。

解题步骤

  1. 创建长度为 1001 的计数表，统计 arr1 的全部元素。
  2. 写指针从零开始，按 arr2 顺序将每个值写到次数用尽。
  3. 按数值从 0 到 1000 扫描计数表，继续写出剩余副本。
  4. 返回已被重新排列的 arr1。

代码实现

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] count = new int[1001];

        for (int value : arr1) {
            count[value]++;
        }

        int index = 0;

        // 先按 arr2 的顺序写完每个值，并同步消耗频次。
        for (int value : arr2) {
            while (count[value] > 0) {
                arr1[index++] = value;
                count[value]--;
            }
        }

        // 剩余频次按数值升序写回。
        for (int value = 0; value < count.length; value++) {
            while (count[value] > 0) {
                arr1[index++] = value;
                count[value]--;
            }
        }

        return arr1;
    }
}

func relativeSortArray(arr1 []int, arr2 []int) []int {
    count := make([]int, 1001)
    for _, value := range arr1 {
        count[value]++
    }

    index := 0
    // 先按 arr2 的顺序写完每个值，并同步消耗频次。
    for _, value := range arr2 {
        for count[value] > 0 {
            arr1[index] = value
            index++
            count[value]--
        }
    }
    // 剩余频次按数值升序写回。
    for value := 0; value < len(count); value++ {
        for count[value] > 0 {
            arr1[index] = value
            index++
            count[value]--
        }
    }
    return arr1
}

复杂度分析

  • 时间复杂度：$O(n+m+C)$，n、m 为两个数组的长度，值域大小 $C=1001$；展开频次共写入 n 个元素。
  • 空间复杂度：$O(C)$，仅额外保存计数表。

关键点总结

[!green]

  • 两个顺序：先按 arr2 的顺序，再按数值顺序。
  • 频次全部消耗完后再处理下一个值，同值才能连续。
  • 完整统计之后才允许覆盖 arr1。

易错点总结

[!yellow]

  • 计数表只分配 1000 项：最大值可以为 1000，必须保留下标 1000，长度应为 1001。
  • 用一次判断代替循环输出：重复值需要按次数全部写出，不能只保存一份。
  • 第一阶段没有减少计数：第二阶段会把已经写过的值再次输出。
  • 统计未完成就覆盖原数组：可能改掉尚未读取的数据，必须先完整统计再写回。
  • 尾部仍按原数组顺序处理：未出现在 arr2 中的值要求升序，应按计数表下标扫描。

相似题目

题目 难度 关联与区别
791. 自定义字符串排序 中等 同样由外部序列规定一部分元素的排序优先级，本题对象是整数而不是字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2022/16595932
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！