LeetCode 697. 数组的度

约 5 分钟
文章信息 7 个分类 2 个标签
分类
LeetCode CodeTop 简单 未解决 2-5 字节 华为
标签
数组 哈希表

题目描述

✅ 697. 数组的度

image-20260928224522121

题意分析

数组的度是其中某个值出现次数的最大值。现在要找一个连续子数组，使它的度与整个原数组相同，并让长度尽可能短；返回这个最短长度。

子数组必须保留原来连续的一段，不能只把相同值抽出来拼在一起。可能有多个值共同达到原数组的最高频次，只需要完整保留其中一个值的所有出现，不要求同时覆盖所有最高频值。

解法：记录首次位置与次数

核心思路

[!blue]

设原数组的度为 D。子数组里的任何值，出现次数都不会超过它在原数组中的次数。因此，要让子数组的度仍为 D，它必须包含某个原本就出现 D 次的值的全部出现；反过来，只要完整覆盖这样一个值，子数组的度就一定达到 D。

对一个固定值，包含全部出现的最短连续范围，就是从它首次出现的位置到最后出现的位置，长度为末次下标减首次下标加一。无需考虑其他边界更宽的区间，只需在所有最高频值对应的这种范围中取最短。

这个计算可以在一趟扫描中完成。count 保存每个值到目前为止的次数，first 只记录首次下标；扫描到当前值时，当前下标就是它在已处理前缀中的最新末次位置，所以不用再单独保存末次位置表。

同时维护当前前缀的度 degree 和达到这个度的最短范围 answer。如果当前值的新频次超过旧度，所有旧候选都已达不到新的频次要求，必须直接用当前范围替换答案；如果新频次等于当前度，只需比较它是否提供更短范围；低于当前度则不影响答案。整个前缀处理完时，这两个状态自然变成全数组的目标。

解题步骤

  1. 初始化次数表、首次下标表、degree = 0，用原数组长度作为答案上界。
  2. 扫描下标 i，当前值首次出现时记录位置，随后将其次数加一。
  3. 计算当前值的覆盖长度 i - first[value] + 1。
  4. 次数超过当前度时，同时更新度和答案；次数并列时只取更短长度。
  5. 返回扫描结束后的最短长度。

代码实现

class Solution {
    public int findShortestSubArray(int[] nums) {
        // count 记出现次数，first 记首次下标，两者合起来就能算出覆盖某个数的最短区间。
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        int degree = 0;
        // 数组非空，整个数组一定是一个合法答案，用它当上界。
        int answer = nums.length;

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];

            // 首次位置只记录一次，当前下标充当末次位置
            first.putIfAbsent(num, i);
            int freq = count.getOrDefault(num, 0) + 1;

            count.put(num, freq);

            int length = i - first.get(num) + 1;

            // 度提高时旧候选不再合法，直接替换长度
            if (freq > degree) {
                degree = freq;
                answer = length;
            } else if (freq == degree) {
                answer = Math.min(answer, length);
            }
        }

        return answer;
    }
}

func findShortestSubArray(nums []int) int {
    // count 记出现次数，first 记首次下标，两者合起来就能算出覆盖某个数的最短区间。
    count := make(map[int]int)
    first := make(map[int]int)
    degree := 0
    // 数组非空，整个数组一定是一个合法答案，用它当上界。
    answer := len(nums)

    for i, v := range nums {
        // 首次位置只记录一次，当前下标充当末次位置
        if _, ok := first[v]; !ok {
            first[v] = i
        }
        count[v]++

        length := i - first[v] + 1
        // 度提高时旧候选不再合法，直接替换长度
        if count[v] > degree {
            degree = count[v]
            answer = length
        } else if count[v] == degree {
            if length < answer {
                answer = length
            }
        }
    }

    return answer
}

复杂度分析

  • 时间复杂度：期望 $O(n)$，只扫描一次，每轮执行常数次哈希读写。
  • 空间复杂度：$O(u)$，u 为不同值的数量，两张表分别保存次数和首次位置。

关键点总结

[!green]

  • 达到原数组的度，等价于完整保留至少一个最高频值的所有出现。
  • 一个值的最短覆盖由首末位置唯一确定，当前扫描下标即可充当末次位置。
  • 新度出现时旧答案失去资格，应直接替换；只有同度候选才能比较长度。

易错点总结

[!yellow]

  • 度增加后仍与旧答案取最小，会保留一个长度虽短但频次不足的区间。
  • 每次出现都覆盖首次下标，会丢掉必须包含的更早出现，低估范围长度。
  • 只看出现次数、不看首末距离，无法确定需要保留多少个中间元素。
  • 将所有最高频值的首末范围合并，会多保留本来不必覆盖的部分。
  • 闭区间长度漏掉加一，会少算一个端点。

相似题目

题目 难度 关联与区别
347. 前 K 个高频元素 中等 同样先统计频次，本题找达到全局最高频次的值，再用首次和最后位置确定最短包含区间。
387. 字符串中的第一个唯一字符 简单 同样结合完整频次与出现位置，本题关注最高频值的首尾，原题关注首个唯一字符。
转载与许可
作者
链接 https://hgnulb.github.io/blog/2024/65870779
许可 本博客所有文章除特别声明外，均采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处！