LC 697. 数组的度
题目描述
这是 LeetCode 上的 697. 数组的度 ,难度为 简单。
给定一个非空且只包含非负数的整数数组 nums,数组的度的定义是指数组里任一元素出现频数的最大值。
你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。
示例 1:1
2
3
4
5
6
7输入:[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输入:[1,2,2,3,1,4,2]
输出:6
提示:
- nums.length 在1到 50,000 区间范围内。
- nums[i] 是一个在 0 到 49,999 范围内的整数。
数组计数
由于已知值的范围是 [0, 49999]
。
我们可以使用数组 cnt
来统计每个值出现的次数,数组 first
和 last
记录每个值「首次出现」和「最后出现」的下标。
同时统计出最大词频为 max
。
然后再遍历一次数组,对于那些满足词频为 max
的数值进行长度计算。
1 |
|
- 时间复杂度:对数组进行常数次扫描。复杂度为 $O(n)$
- 空间复杂度:$O(n)$
哈希表计数
同样的,除了使用静态数组,我们还可以使用哈希表进行计数。
1 |
|
- 时间复杂度:对数组进行常数次扫描。复杂度为 $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 原题链接和其他优选题解。
本博客所有文章除特别声明外,均采用 CC BY-SA 4.0 协议 ,转载请注明出处!