[java/python3]leetcode 1838. Frequency of the Most Frequent Element

Frequency of the Most Frequent Element - LeetCode

Frequency of the Most Frequent Element - LeetCode

문제

최대 빈도수 구하기 문제. 

 

풀이

투 포인터를 사용한 윈도우 슬라이드 를 유지하면서 풀이를 하였다.

원리는 다음과 같다. 

1. O(N)으로 움직이는 left 와 right 포인터 를 생성한 후 초기값은 둘다 0 이다.
2. 주어진 배열을 오름차순 정렬.
3. nums [ right ] 는 범위 [ left..right ] 에서 빈도수 기준이 되는 수이다.
4. sum 은 윈도우 슬라이드 내의 누적합 sum 이다.
5. max_sum = 현재 윈도우 슬라이드내에서 최대 누적합 = sum + k 
6. max_sum < 현재 윈도우 슬라이드  길이 * 윈도우 슬라이드 원소 최대값  이면 left 포인터를 움직인다.
7. 각 반복마다. answer 갱신 후 답 도출.

투 포인터 left 와 right 를 사용하여 left, right 둘다 한 번씩만 배열길이 만큼 탐색함으로 시간 복잡도는 :  O(N)이다. 

 

위 수도 코드 6번에 대한 보충 설명이다.

nums[right] * (right - left + 1) > sum + k

현재 윈도우 슬라이드에서 빈도수를 맞추는 기준은 nums[right] 이다. 그러면 모두 같은 원소가 된 후의 윈도우 슬라이드 (범위 from left to right ) 내의 누적합은 nums[right] * 윈도우 슬라이드 길이 가 된다. 따라서 위와 같은 조건에 따라 윈도우 슬라이드 사이즈를 조정한다. 

 

주의 !! 자바에서는 sum 변수 자료형이 long이 아니면 overflow가 발생한다. 잊지말것.

 

코드

파이썬

class Solution:
    def maxFrequency(self, nums: List[int], k: int) -> int:
        nums.sort()
        left = 0
        right = 0
        sum = 0 
        ans = 0
        while right < len(nums):
            sum += nums[right]
            while nums[right] * (right - left + 1) > sum + k:
                sum -=nums[left]
                left+=1
                
            ans = max(ans, right - left + 1)
            right+=1
        return ans

자바

class Solution {
    public int maxFrequency(int[] nums, int k) {
        Arrays.sort(nums);
        int answer = 0;
        long sum =0;
        int left =0 ;
        for(int right = 0 ; right< nums.length; right++){
            sum += nums[right];

            //left right 까지 합이 만들수 있는 합보다 크면 left증가
            while(nums[right] * (right - left + 1) > sum + k){
                sum -= nums[left++];
            }
            answer = Math.max(answer, right- left + 1);
        }
        return answer;
    }
}