给定一个非空且只包含非负数的整数数组 nums,数组的 度 的定义是指数组里任一元素出现频数的最大值。 你的任务是在 nums 中找到与 nums 拥有相同大小的度的最短连续子数组,返回其长度。
时间: 2024-04-21 09:23:07 浏览: 11
你可以使用以下方法来解决这个问题:
首先,遍历数组 nums 并使用一个字典 freq 来记录每个元素的出现次数。同时,使用另一个字典 start 来记录每个元素第一次出现的索引位置。
接下来,我们需要找到度数最大的元素。为此,我们遍历 freq 字典并找到最大的频数 max_freq。
然后,我们再次遍历 freq 字典,找到所有频数等于 max_freq 的元素,并计算它们的最短连续子数组长度。具体做法是,对于频数等于 max_freq 的元素,计算它们的最右索引减去最左索引加一的值,并记录这个值的最小值。
最后,返回记录的最小值作为结果。
下面是使用 Python 实现的代码:
```python
def findShortestSubArray(nums):
freq = {}
start = {}
max_freq = 0
min_length = float('inf')
for i, num in enumerate(nums):
freq[num] = freq.get(num, 0) + 1
if num not in start:
start[num] = i
if freq[num] > max_freq:
max_freq = freq[num]
for num, count in freq.items():
if count == max_freq:
length = start[num] + freq[num] - 1 - start[num] + 1
min_length = min(min_length, length)
return min_length
```
这个算法的时间复杂度为 O(n),其中 n 是数组 nums 的长度。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)