LeetCode.697.Degree of an Array 度数相同的最小连续子数组

题目描述

697 Degree of an Array https://leetcode-cn.com/problems/degree-of-an-array/

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: [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: [1,2,2,3,1,4,2]
Output: 6

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

解题过程

数组的度：数组里任一元素出现频数的最大值。出现频率最大的数可能有多个。 找和原数组度数相同的最小连续子数组，也就是频率最大数的第一次出现位置和最后一次出现位置之间的子数组，如果频率最大数有多个，找收尾间隔最短的。

遍历一遍数组即可统计每个数的 出现次数, 第一次出现的index, 最后一次出现的index 然后遍历统计结果，找出现次数最多的元素的首尾距离，出现次数一样多的，找首尾距离最短的。

时间复杂度 O(n) 空间复杂度 O(n)

private static class SolutionV2020 {
    public int findShortestSubArray(int[] nums) {
        if (null == nums || nums.length == 0) {
            return 0;
        }
        // 数组元素n -> 出现次数, 第一次出现的index, 最后一次出现的index
        Map<Integer, List<Integer>> map = new HashMap<>();
        // 第一次遍历，统计数组中每个元素的出现次数和首尾距离
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(nums[i])) {
                List<Integer> list = map.get(nums[i]);
                list.set(0, list.get(0) + 1);
                if (list.size() == 2) {
                    list.add(i);
                } else {
                    list.set(2, i);
                }
            } else {
                List<Integer> list = new ArrayList(3);
                list.add(1);
                list.add(i);
                map.put(nums[i], list);
            }
        }
        int maxTimes = 0;
        int minLength = 0;
        // 遍历统计结果，找出现次数最多的元素的首尾距离
        for (Map.Entry<Integer, List<Integer>> entry : map.entrySet()) {
            List<Integer> list = entry.getValue();
            if (list.get(0) > maxTimes) {
                maxTimes = list.get(0);
                minLength = list.size() == 3 ? list.get(2) - list.get(1) + 1 : 1;
            } else if (list.get(0) == maxTimes) {
                // 出现次数一样多的，找首尾距离最短的
                int thisLength = list.size() == 3 ? list.get(2) - list.get(1) + 1 : 1;
                minLength = Math.min(thisLength, minLength);
            }
        }
        return minLength;
    }
}

GitHub代码

algorithms/leetcode/leetcode/_697_DegreeOfArray.java https://github.com/masikkk/algorithms/blob/master/leetcode/leetcode/_697_DegreeOfArray.java