# LWC 54：697. Degree of an Array

## LWC 54：697. Degree of an Array

Problem:

Given a non-empty array of non-negative integers nums, the degree of this array is defined as the maximum frequency of any one of its elements. Your task is to find the smallest possible length of a (contiguous) subarray of nums, that has the same degree as nums.

Example 1:

Input: [1, 2, 2, 3, 1] Output: 2 Explanation: The input array has a degree of 2 because both elements 1 and 2 appear twice. Of the subarrays that have the same degree: [1, 2, 2, 3, 1], [1, 2, 2, 3], [2, 2, 3, 1], [1, 2, 2], [2, 2, 3], [2, 2] The shortest length is 2. So return 2.

Example 2:

Input: [1,2,2,3,1,4,2] Output: 6

Note:

nums.length will be between 1 and 50,000.

nums[i] will be an integer between 0 and 49,999.

```    public int findShortestSubArray(int[] nums) {
if (!lf.containsKey(nums[i])) lf.put(nums[i], i);
rt.put(nums[i], i);
cnt.put(nums[i], cnt.getOrDefault(nums[i], 0) + 1);
}

int degree = Collections.max(cnt.values());
int ans = Integer.MAX_VALUE;
for (int key : cnt.keySet()) {
if (degree == cnt.get(key)) {
ans = Math.min(ans, rt.        Map<Integer, Integer> lf  = new HashMap<>();
Map<Integer, Integer> rt  = new HashMap<>();
Map<Integer, Integer> cnt = new HashMap<>();

for (int i = 0; i < nums.length; ++i) {
get(key) - lf.get(key) + 1);
}
}
return ans;
}```

```    public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> map = new HashMap<>();
int max = 0;
for (int num : nums) {
map.put(num, map.getOrDefault(num, 0) + 1);
}

for (int key : map.keySet()) {
max = Math.max(max, map.get(key));
}

int ans = 1 << 29;
Map<Integer, Integer> cnt = new HashMap<>();
int lf = 0, rt = 0;
int window = 0;
for (;;) {
while (rt < nums.length && window != max) {
cnt.put(nums[rt], cnt.getOrDefault(nums[rt], 0) + 1);
window = Math.max(window, cnt.get(nums[rt]));
rt ++;
}
if (window != max) break;
ans = Math.min(ans, rt - lf);
cnt.put(nums[lf], cnt.get(nums[lf]) - 1);
lf ++;
window = Collections.max(cnt.values());
}
return ans;
}      ```

98 篇文章33 人订阅

0 条评论

## 相关文章

1859

### Java中list<Object[]>、list<Student>、list<Map<String,String>>排序

1：list<Object[]>的排序 public static void main(String[] args) { // TODO Auto-gene...

3378

915

2184

792

### 【Java入门提高篇】Day19 Java容器类详解（二）Map接口

上一篇里介绍了容器家族里的大族长——Collection接口，今天来看看容器家族里的二族长——Map接口。

24719

551

1828

### Java集合深度解析之HashMap

HashMap简介 HashMap是基于哈希表实现的，每一个元素是一个key-value对，其内部通过单链表解决冲突问题，容量不足（超过了阀值）时，同样会自动增...

3435

### 使用Swagger生成Spring Boot微服务API文档

springfox是产生API文档，而swagger-ui 则是RestAPI的界面。 创建一个RestController ，定义API:

1002