LeetCode 697. 数组的度

Categories:

题目描述
思路分析
1. 解法一：记录首尾位置与次数（推荐）
相似题目

题目描述

✅ 697. 数组的度

思路分析

解法一：记录首尾位置与次数（推荐）

核心思路：

遍历数组，记录每个数字的出现次数、首次出现位置、最后一次出现位置。

数组的度为最大出现次数。

在所有达到度的数字中取最小的 last - first + 1。

复杂度分析：

时间复杂度：O(n)，其中 n 表示数组长度。

空间复杂度：O(n)，用于哈希表。

import java.util.HashMap;
import java.util.Map;

class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> count = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>();
        Map<Integer, Integer> last = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            int num = nums[i];
            count.put(num, count.getOrDefault(num, 0) + 1);
            first.putIfAbsent(num, i);
            last.put(num, i);
        }

        int degree = 0;
        for (int c : count.values()) {
            degree = Math.max(degree, c);
        }

        int ans = nums.length;
        for (int num : count.keySet()) {
            if (count.get(num) == degree) {
                ans = Math.min(ans, last.get(num) - first.get(num) + 1);
            }
        }

        return ans;
    }
}

func findShortestSubArray(nums []int) int {
	count := make(map[int]int)
	first := make(map[int]int)
	last := make(map[int]int)

	for i, v := range nums {
		count[v]++
		if _, ok := first[v]; !ok {
			first[v] = i
		}
		last[v] = i
	}

	degree := 0
	for _, c := range count {
		if c > degree {
			degree = c
		}
	}

	ans := len(nums)
	for num, c := range count {
		if c == degree {
			length := last[num] - first[num] + 1
			if length < ans {
				ans = length
			}
		}
	}

	return ans
}

相似题目

题目	难度	考察点
169. 多数元素	简单	计数
229. 多数元素 II	中等	计数
347. 前 K 个高频元素	中等	计数
442. 数组中重复的数据	中等	计数
448. 找到所有数组中消失的数字	简单	计数

本文作者: HGNULB

本文链接: https://hgnulb.github.io/blog/2024/65870779