【数组篇】day07_697. 数组的度
【摘要】 给定一个非空且只包含非负数的整数数组 nums，数组的 度 的定义是指数组里任一元素出现频数的最大值。你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。 示例 1：输入：nums = [1,2,2,3,1]输出：2解释：输入数组的度是 2 ，因为元素 1 和 2 的出现频数最大，均为 2 。连续子数组里面拥有相同度的有如下所示：[1, 2, 2, 3,...
给定一个非空且只包含非负数的整数数组 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范围内的整数。
【题解】
题解一：
思路：
- dict统计数组中元素个数，找出最大的元素
- 最大的元素中起始和结束位置间隔最短的距离即为所求值
复杂度：
- 时间复杂度：O(n)
- 空间复杂度：O(n)
class Solution {
public int findShortestSubArray(int[] nums) {
// dict记录元素次数
Map<Integer, Integer> dict = new HashMap<>();
int max = 0;
for (int num : nums) {
int value = dict.getOrDefault(num, 0) + 1;
dict.put(num, value);
max = Math.max(max, value);
}
// 求度最大的元素中起始和结束位置最短的距离
int result = Integer.MAX_VALUE;
for (Map.Entry<Integer, Integer> entry : dict.entrySet()) {
int value = entry.getValue();
if (value != max) {
continue;
}
result = Math.min(result, findInterval(entry.getKey(), nums));
}
return result;
}
/**
* 查找元素在数组中起始和结束位置的间隔
*
* @param target
* @param nums
* @return
*/
private int findInterval(int target, int[] nums) {
int start = 0, end = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] == target) {
start = i;
break;
}
}
for (int i = nums.length - 1; i >= 0; i--) {
if (nums[i] == target) {
end = i;
break;
}
}
return end - start + 1;
}
}
【版权声明】本文为华为云社区用户原创内容，转载时必须标注文章的来源（华为云社区）、文章链接、文章作者等基本信息， 否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容，欢迎发送邮件进行举报，并提供相关证据，一经查实，本社区将立刻删除涉嫌侵权内容，举报邮箱：
cloudbbs@huaweicloud.com
- 点赞
- 收藏
- 关注作者
评论（0）