数组的度

发表于
本文字数： 2.7k 阅读时长 ≈ 2 分钟

LeetCode每日一题，697. Degree of an Array

先看题目描述

y4zASS.png

大意就是给定一个数组 nums，再告诉我们数组的度的定义是数组中元素出现的频数的最大值，我们需要找出 nums 中与其度相等的最小连续子数组，并返回其长度

算法和思路

滑动窗口

因为看到题目说找出最小的连续子数组的长度，就想到用滑动窗口做

我们首先定义滑动窗口的度，和数组的度的定义相同，即窗口内元素出现频数的最大值

先求出数组 nums 的度 degree，接下来我们先初始化长度为 0 的滑动窗口，即 left = 0，right = 0，然后我们移动 right 指针来扩张滑动窗口，直至滑动窗口的度达到 degree 时停止滑动窗口的扩张，然后移动 left 指针来收缩滑动窗口直至滑动窗口的度刚好小于 degree。接下来只需重复进行两种操作，当滑动窗口的度小于 degre时，同时移动 left 指针和 right 指针来移动滑动窗口；当滑动窗口的度等于 degree 时，移动 left 指针来收缩滑动窗口。过程中要一直维护滑动窗口的度，最后返回滑动窗口的大小即可

滑动窗口方法的实现细节比较多，具体看代码吧，注意滑动窗口内至多只有一个元素的频数可以达到 degree

算法源码

滑动窗口

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public int findShortestSubArray(int[] nums) {
        int len = nums.length;
        int[] cnt = new int[50000];
        int degree = 0;
        for (int num : nums) {
            cnt[num]++;
            degree = Math.max(degree, cnt[num]);
        }
        int left = 0;
        int right = 0;
        Arrays.fill(cnt, 0);
        while (true) {
            cnt[nums[right]]++;
            if (cnt[nums[right]] == degree) {
                break;
            }
            right++;
        }
        right++;
        int cur = degree;
        while (right <= len) {
            cnt[nums[left]]--;
            if (cnt[nums[left]] == degree - 1) {
                cur--;
            }
            left++;
            if (cur < degree) {
                if (right < len) {
                    cnt[nums[right]]++;
                    cur = Math.max(cur, cnt[nums[right]]);
                }
                right++;
            }
        }
        return right - left;
    }
}

哈希表

这个是题解看到的方法，大致就是求出所有频数和数组的度相等的元素，然后返回这些元素的最晚出现位置和最早出现位置之差的最小值，使用哈希表这个数据结构来实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int findShortestSubArray(int[] nums) {
        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]++;
                map.get(nums[i])[2] = i;
            } else {
                map.put(nums[i], new int[]{1, i, i});
            }
        }
        int maxNum = 0, 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;
    }
}