关于leetcode:leetcode-697-Degree-of-an-Array-数组的度简单

8次阅读

共计 1378 个字符，预计需要花费 4 分钟才能阅读完成。

https://leetcode.cn/problems/…

给定一个非空且只蕴含非正数的整数数组 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 范畴内的整数。

首先给数组的度下一个定义，给一个数组，某个或某些数字呈现最多的次数为该数组的度。题目要求咱们找到最短的子数组使其和原数组领有雷同的度。

思路：统计每个数字呈现的次数，用哈希来建设数字与呈现次数的映射，咱们要求与该数组有雷同度的最小长度子数组，咱们要晓得每个数字的度，与其首次呈现的地位，这样咱们要定义两个哈希一个来存呈现的次数，一个来存首次呈现的地位。咱们再定义一个变量 degree 来示意数组的度。遍历数组以后遍历地位能够看作是最初一次呈现的地位即尾地位，累加以后数字呈现的次数，如果数字是第一次呈现，建设数字与首地位的映射，如果以后数字的呈现次数等于 degree 时，以后地位为尾地位，用 endIndex – startIndex + 1 来更新后果；如果以后数字的呈现次数大于 degree，阐明之前的后果代表的数字不是呈现最多的，间接将后果更新为 endIndex – startIndex + 1，而后 degree 也更新为以后数字呈现的次数。

public class Solution {public int findShortestSubArray(int[] nums) {Map<Integer, Integer> countMap = new HashMap<>();
        Map<Integer, Integer> firstIdxMap = new HashMap<>();
        int ans = nums.length;
        int degree = 0;
        for (int i = 0; i < nums.length; i++) {int num = nums[i];
            countMap.put(num, countMap.getOrDefault(num, 0) + 1);
            // 记录首地位
            if (countMap.get(num) == 1) {firstIdxMap.put(num, i);
            }

            if (countMap.get(num) == degree) {ans = Math.min(ans, i - firstIdxMap.get(num) + 1);
            } else if (countMap.get(num) > degree) {ans = i - firstIdxMap.get(num) + 1;
                degree = countMap.get(num);
            }
        }
        return ans;
    }
}