[LeetCode/Easy] 697. Degree of an Array

1. Input

1) int[] nums

 

2. Output

1) nums에서 가장 많이 있는 요소의 빈도 수를 nums의 정도라고 표현할 때, nums의 정도와 같은 정도를 가진 부분 배열 중 가장 작은 부분 배열의 길이를 반환

- 부분 배열은 연속적이어야 한다.

 

3. Constraint

1) 1 <= nums.length <= 50,000

2) 0 <= nums[i] <= 49,999

 

4. Example

Input: nums = [1,2,2,3,1] -> Output: 2

설명: 1과 2가 2번씩 등장하므로 nums의 정도는 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를 반환한다.

 

5. Code

1) 첫 코드(2023/05/29)

class Solution {
    public int findShortestSubArray(int[] nums) {
        HashMap<Integer,Integer> m = new HashMap<>();
        int max = 0;
        for(int i : nums){
            m.put(i, m.getOrDefault(i,0)+1);
            max = Math.max(max, m.get(i));
        }
        List<Integer> list = new ArrayList<>();
        for(int i : m.keySet()){
            if(m.get(i)==max)
                list.add(i);
        }
        int ans = nums.length;
        for(int i=0 ; i<list.size() ; i++){
            int front = 0, back = nums.length-1;
            for(int j=0 ; j<nums.length ; j++)
                if(nums[j]==list.get(i)){
                    front = j; break;
                }
            for(int j=back ; j>=0 ; j--)
                if(nums[j]==list.get(i)){
                     back = j; break;
                }
            ans = Math.min(ans, back-front+1);
        }        
        return ans;
    }
}

- 8%, 61%