Leetcode-697-数组的度

Leecode-697-数组的度

题目描述

• 给定一个非空且只包含非负数的整数数组 nums，数组的度的定义是指数组里任一元素出现频数的最大值。

• 你的任务是在 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 范围内的整数。

思路：哈希表+贪心

• 记原数组中出现次数最多的数为 x，那么和原数组的度相同的最短连续子数组，必然包含了原数组中的全部 x，且两端恰为 x 第一次出现和最后一次出现的位置。
• 因为符合条件的 x可能有多个，即多个不同的数在原数组中出现次数相同。所以为了找到这个子数组，我们需要统计每一个数出现的次数，同时还需要统计每一个数第一次出现和最后一次出现的位置。
  • 使用哈希表实现该功能，每一个数映射到一个长度为 3 的数组，
  • 数组中的三个元素分别代表这个数出现的次数、这个数在原数组中第一次出现的位置和这个数在原数组中最后一次出现的位置。
• 当我们记录完所有信息后，我们需要遍历该哈希表，找到元素出现次数最多，且前后位置差最小的数。

class Solution {
    public int findShortestSubArray(int[] nums) {
        // 1. 哈希表记录：遍历一次哈希表
            // 1.数字出现的次数
            // 2.该数字第一次出现的下标
            // 3.该数字最后一次出现的下标
        Map<Integer,int[]> map = new HashMap<Integer,int[]>();
        int n = nums.length;
        for(int i = 0;i < n;i++){
            if(map.containsKey(nums[i])){
                map.get(nums[i])[0]++;                      // 当前数字出现次数加1
                map.get(nums[i])[2] = i;                    // 更新出现的最后一次下标
            }else{
                map.put(nums[i],new int[]{1,i,i});
            }
        }

        // 2. 统计哈希表
        int maxNum = 0;                                     // 出现次数最多的数字
        int minLen = 0;                                     // 第一次出现和最后一次出现的间隔
        for(Map.Entry<Integer,int[]> entry:map.entrySet()){
            int[] arr = entry.getValue();                   // 遍历哈希表拿到每个数字对应的数组
            if(maxNum < arr[0]){                            // 如果不是出现次数最多的
                maxNum = arr[0];
                minLen = arr[2] - arr[1] + 1;
            }else if(maxNum == arr[0]){                     // 如果出现次数是最多的数字
                if(minLen > arr[2] - arr[1] + 1){
                    minLen = arr[2] - arr[1] + 1;
                }
            }
        }
        return minLen;                                      // 返回子数组长度
    }
}

复杂度分析

• 时间复杂度：O(n)，其中 n 是原数组的长度，我们需要遍历原数组和哈希表各一次，它们的大小均为 O(n)。

• 空间复杂度：O(n)，其中 n 是原数组的长度，最坏情况下，哈希表和原数组等大。

打赏