Leetcode

# 697. Degree of an Array

by hooni posted May 05, 2020
?

#### 단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

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.

• ```class Solution {
public int findShortestSubArray(int[] nums) {
Map<Integer, Integer> hmap = new HashMap<>();

int degree = -1;
//int number = nums[0];

for(int num : nums){
int count = hmap.getOrDefault(num, 0) + 1;
if(degree < count){
degree = count;
//number = num;
}
hmap.put(num, count);
}

int minVal = Integer.MAX_VALUE;

for(Map.Entry<Integer, Integer> item : hmap.entrySet()){
if(item.getValue() == degree){
int number = item.getKey();
int left = -1;
int right = -1;
int len = nums.length;
for(int i=0; i<len; i++){
if(nums[i] == number && left == -1){
left = i;
}

if(nums[len-1-i] == number && right == -1){
right = len - 1 - i;
}
}

len = right < left ? 0 : right - left + 1;
if(minVal > len){
minVal = len;
}
}
}

return minVal;
}
}```

1 2 3 4