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;
}
}
[문제] https://leetcode.com/problems/degree-of-an-array/
