LC 697. 数组的度

题目描述

这是 LeetCode 上的 697. 数组的度 ，难度为 简单。

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

你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组，返回其长度。

示例 1：

1
2
3
4
5
6
7
8
9
输入：[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
3
输入：[1,2,2,3,1,4,2]

输出：6

提示：

  • nums.length 在 1 到 50000 区间范围内。
  • nums[i] 是一个在 0 到 49999 范围内的整数。

数组计数

由于已知值的范围是 $[0, 49999]$。

我们可以使用数组 cnt 来统计每个值出现的次数，数组 first 和 last 记录每个值「首次出现」和「最后出现」的下标。

同时统计出最大词频为 max。

然后再遍历一次数组，对于那些满足词频为 max 的数值进行长度计算。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    int N = 50010;
    public int findShortestSubArray(int[] nums) {
        int n = nums.length, max = 0, ans = 0x3f3f3f3f;
        int[] cnt = new int[N];
        int[] first = new int[N], last = new int[N];
        Arrays.fill(first, -1);
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            max = Math.max(max, ++cnt[t]);
            if (first[t] == -1) first[t] = i;
            last[t] = i;
        }
        for (int t : nums) {
            if (cnt[t] == max) ans = Math.min(ans, last[t] - first[t] + 1);
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int N = 50010;
    int findShortestSubArray(vector<int>& nums) {
        int n = nums.size(), maxv = 0, ans = 0x3f3f3f3f;
        vector<int> cnt(N, 0);
        vector<int> first(N, -1), last(N, -1);
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            maxv = max(maxv, ++cnt[t]);
            if (first[t] == -1) first[t] = i;
            last[t] = i;
        }
        for (auto& t : nums) {
            if (cnt[t] == maxv) ans = min(ans, last[t] - first[t] + 1);
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
    def __init__(self):
        self.N = 50010

    def findShortestSubArray(self, nums):
        n, maxv, ans = len(nums), 0, 0x3f3f3f3f
        cnt = [0] * self.N
        first, last = [-1] * self.N, [-1] * self.N
        for i, t in enumerate(nums):
            cnt[t] += 1
            maxv = max(maxv, cnt[t])
            if first[t] == -1:
                first[t] = i
            last[t] = i
        for t in nums:
            if cnt[t] == maxv:
                ans = min(ans, last[t] - first[t] + 1)
        return ans

  • 时间复杂度：对数组进行常数次扫描。复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

哈希表

同样的，除了使用静态数组，我们还可以使用哈希表进行计数。

Java 代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findShortestSubArray(int[] nums) {
        int n = nums.length, max = 0, ans = 0x3f3f3f3f;
        Map<Integer, Integer> cnt = new HashMap<>();
        Map<Integer, Integer> first = new HashMap<>(), last = new HashMap<>();
        for (int i = 0; i < n; i++) {
            int t = nums[i];
            cnt.put(t, cnt.getOrDefault(t, 0) + 1);
            max = Math.max(max, cnt.get(t));
            if (!first.containsKey(t)) first.put(t, i);
            last.put(t, i);
        }
        for (int t : nums) {
            if (cnt.get(t) == max) ans = Math.min(ans, last.get(t) - first.get(t) + 1);
        }
        return ans;
    }
}

C++ 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int findShortestSubArray(vector<int>& nums) {
        int n = nums.size(), maxv = 0, ans = 0x3f3f3f3f;
        unordered_map<int, int> cnt;
        unordered_map<int, int> first, last;
        for (int i = 0; i < n; ++i) {
            int num = nums[i];
            cnt[num] += 1;
            maxv = max(maxv, cnt[num]);
            if (first.find(num) == first.end()) first[num] = i;
            last[num] = i;
        }
        for (auto& t : nums) {
            if (cnt[t] == maxv) ans = min(ans, last[t] - first[t] + 1);
        }
        return ans;
    }
};

Python 代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution:
    def findShortestSubArray(self, nums: List[int]) -> int:
        n, maxv, ans = len(nums), 0, 0x3f3f3f3f
        count = {}
        first, last = {}, {}
        for i, num in enumerate(nums):
            count[num] = count.get(num, 0) + 1
            maxv = max(maxv, count[num])
            if num not in first:
                first[num] = i
            last[num] = i
        for t in nums:
            if count[t] == maxv:
                ans = min(ans, last[t] - first[t] + 1)
        return ans

  • 时间复杂度：对数组进行常数次扫描。复杂度为 $O(n)$
  • 空间复杂度：$O(n)$

总结

我们知道 哈希表 = 哈希函数 + 数组，由于哈希函数计算需要消耗时间（Java 中首先涉及自动装箱/拆箱，之后还要取对象的 hashCode 进行右移异或，最后才计算哈希桶的下标），以及处理哈希冲突的开销。

其效率必然比不上使用我们静态数组进行计数。

因此我建议，对于那些 数值范围确定且不太大（$10^6$ 以内都可以使用，本题数量级在 $10^4$） 的计算场景，使用数组进行计数，而不是使用哈希表。

最后

这是我们「刷穿 LeetCode」系列文章的第 No.697 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。