697. 数组的度

🟢 🔖 数组 哈希表 🔗 力扣open in new window LeetCodeopen in new window

题目

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements.

Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: nums = [1,2,2,3,1]
Output: 2
Explanation:
The input array has a degree of 2 because both elements 1 and 2 appear twice.
Of the subarrays that have the same degree:
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
The shortest length is 2. So return 2.

Example 2:

Input: nums = [1,2,2,3,1,4,2]
Output: 6
Explanation:
The degree is 3 because the element 2 is repeated 3 times.
So [2,2,3,1,4,2] is the shortest subarray, therefore returning 6.

Constraints:

nums.length will be between 1 and 50,000.
nums[i] will be an integer between 0 and 49,999.

题目大意

给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

输入： nums = [1,2,2,3,1]
输出： 2
解释：
输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。
连续子数组里面拥有相同度的有如下所示：
[1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2]
最短连续子数组 [2, 2] 的长度为 2 ，所以返回 2 。

示例 2：

输入： nums = [1,2,2,3,1,4,2]
输出： 6
解释：
数组的度是 3 ，因为元素 2 重复出现 3 次。
所以 [2,2,3,1,4,2] 是最短子数组，因此返回 6 。

提示：

nums.length 在 1 到 50,000 范围内。
nums[i] 是一个在 0 到 49,999 范围内的整数。

解题思路

遍历数组遍历数组一次，收集一下信息：

每个元素在数组中第一次（start）和最后一次出现的位置（end）。
每个元素在数组中的出现次数（count）。

确定度和满足条件的元素

根据 count 的最大值，找到数组的度 degree。
找出所有度等于 degree 的元素。

计算最短子数组

对于每个满足条件的元素，计算其子数组的长度：子数组长度 = end[元素] - start[元素] + 1
找出这些长度中的最小值。

复杂度分析

时间复杂度：O(n)，其中 n 是数组的长度，遍历数组一次，遍历 count 一次（最多 n 个元素）。
空间复杂度：O(n)，用于存储 count、start 和 end。

代码

/**
 * @param {number[]} nums
 * @return {number}
 */
var findShortestSubarray = function (nums) {
	let count = {},
		start = {},
		end = {};
	let degree = 0;

	for (let i = 0; i < nums.length; i++) {
		let num = nums[i];
		if (start[num] === undefined) start[num] = i; // 记录起始位置
		end[num] = i; // 记录结束位置
		count[num] = (count[num] || 0) + 1; // 统计频数
		degree = Math.max(degree, count[num]); // 更新度
	}

	let minLength = Infinity;
	// 遍历每个元素，找出度为 degree 的最短子数组
	for (let num in count) {
		if (count[num] === degree) {
			minLength = Math.min(minLength, end[num] - start[num] + 1);
		}
	}

	return minLength;
};

697. 数组的度

# 697. 数组的度

# 题目

# 题目大意

# 解题思路

# 复杂度分析

# 代码

# 相关题目

697. 数组的度

题目

题目大意

解题思路

复杂度分析

代码

相关题目