【算法题解】40. 数组的度

❝

这是一道 「简单」 题
https://leetcode.cn/problems/degree-of-an-array/

❞

题目

给定一个非空且只包含非负数的整数数组 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 。

提示：

在到范围内。
是一个在到范围内的整数。

题解

以题目给定的为例，出现次数最多的是 元素2，且出现次数是 3，所以给定数组的度是 3 。

因为要求子数组的度和给定原数组的度相同，所以子数组必须包含所有的 元素2，也就是上图中「绿色背景」的部分。然后求得绿色部分的长度就是本题的答案。

首先求数组的度，必须要循环遍历数组中的每个元素，并对其计数。使用 「哈希表」，key 为元素，value 为出现的次数。

其次，当找到出现次数最多的元素后，我们还需要知道它的起始位置 start 和结束位置 end, 才能计算答案。这个时候我们还需要循环遍历一次给定数组。

既然用了两次循环，那么肯定得想办法把他们合并一下呀！不然怎么说的过去嘛！

所以我们就只用一个循环来解题，将 value 变成一个数组：

value[0] 存放出现的次数，出现一次加个一。
value[1] 存放起始位置，第一次出现时直接记录，后续无需更新。
value[2] 存放结束位置，每次出现都更新一遍。

循环遍历给定数组，并在一个哈希表中记录好次数和位置后。然后再循环遍历一下这个哈希表，求得数组的度的同时，就可以一并将起始位置和结束位置一起求出来啦。

需要注意的是，如果原数组中某几个元素出现的次数相同，且都是最大值，如示例一中的 1 和 2。那么每个都取一遍结果，然后取其中的最小值。

Java 代码实现

class Solution {
    private static final Map<Integer, Integer> duMap = new HashMap<>();

    public int findShortestSubArray(int[] nums) {
        // key 存放数据中的元素，value 长度为3，依次存放出现次数、起始位置、结束位置
        Map<Integer, int[]> indexMap = new HashMap<>();

        for(int i = 0; i < nums.length; i++){
            Integer element = nums[i];
            if(indexMap.containsKey(element)){
                // 更新次数
                indexMap.get(element)[0]++;
                // 更新结束位置
                indexMap.get(element)[2] = i;
            }else{
                indexMap.put(element, new int[]{1, i, i});
            }
        }
        
        int count = -1;
        int ans = nums.length;
        for(int[] value : indexMap.values()){
            if(value[0] > count){
                count = value[0];
                ans = value[2] - value[1] + 1;
            }else if(value[0] == count){
                ans = Math.min((value[2] - value[1] + 1), ans);
            }
        }
        return ans;
    }


}

Go 代码实现


func findShortestSubArray(nums []int) int {

    indexMap := make(map[int][]int, 0)

    for i, v := range nums {
        if element, has := indexMap[v]; has {
            element[0]++
            element[2] = i
        } else {
            indexMap[v] = []int{1, i, i}
        }
    }
    count, ans := -1, len(nums)
    
    for _, element := range indexMap {
        if element[0] > count {
            count, ans = element[0], element[2] - element[1] + 1
        } else if element[0] == count {
            ans = min(ans, element[2] - element[1] + 1)
        }
    }
    return ans
}

func min(a, b int) int {
    if a < b {
        return a
    }
    return b
}