【LeetCode】第697题：数组的度（字节跳动面试题）

今天药忘吃喽~ 2021-12-07 09:47 236阅读 0赞

**题目：给定一个非空且只包含非负数的整数数组 nums, 数组的度的定义是指数组里任一元素出现频数的最大值。你的任务是找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。**

> 示例 1:
> 
> 输入: \[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:
> 
> 输入: \[1,2,2,3,1,4,2\]  
> 输出: 6

注意:

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

*  ###  代码实现 ###

首先需要找到数组中出现次数最多的数，并且还需要知道它们在数组中第一次和最后一次出现的位置。需要注意的是出现次数最多的数可能并不唯一，那就需要比较它们在原数组中代表的子数组哪个小就取哪个。

下面用桶实现，O(N) 的时间复杂度：

public class FindShortestSubArray_697 {
    
        public int findShortestSubArray(int[] nums) {
    
            if(nums == null || nums.length < 1){
                return 0;
            }
    
            // 找到数组中最大元素的值
            int maxVal = -1;
            for(int i = 0; i < nums.length; i++){
                if(nums[i] > maxVal){
                    maxVal = nums[i];
                }
            }
    
            // 创建 max + 1 个桶
            int[] counts = new int[maxVal + 1];      // 存储数组元素出现的次数
            int[] beginIndex = new int[maxVal + 1];  // 存储元素的起始下标
            int[] endIndex = new int[maxVal + 1];    // 存储元素的结束下标
    
            for(int i = 0; i < nums.length; i++){
                if(counts[nums[i]] == 0){
                    beginIndex[nums[i]] = i;
                }
                counts[nums[i]]++;
                // 结束位置都是遇到就更新，这样就可以记录到最后一次出现的位置
                endIndex[nums[i]] = i;
            }
    
            // 查找元素出现次数最多(count[i]最大)，且长度最短（endIndex[i] - beginIndex[i]最小）的长度
            int minSubLength = Integer.MAX_VALUE;
            int maxCount = 0;
            for(int i = 0; i < counts.length; i++){
                int subLen = endIndex[i] - beginIndex[i];
                if(counts[i] > maxCount){
                    maxCount = counts[i];
                    minSubLength = subLen;
                }else if(counts[i] == maxCount && subLen < minSubLength){
                    // 要考虑出现次数相等，但是子数组长度不同的情况
                    minSubLength = subLen;
                }
            }
        return minSubLength + 1;
        }
    }