Leetcode 347. Top K Frequent Elements

347. Top K Frequent Elements

문제

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

---

정수 배열 nums와 정수 k가 주어졌을 때, k개의 가장 빈번한 요소를 반환합니다. 답을 어떤 순서로 반환해도 상관없습니다.

---

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Constraints:

• 1 <= nums.length <= 105
• -104 <= nums[i] <= 104
• k is in the range [1, the number of unique elements in the array].
• It is guaranteed that the answer is unique.

나의 해답

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

		List<Integer>[] count = new ArrayList[nums.length + 1];

		for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
			if (count[entry.getValue()] == null) {
				List<Integer> valueList = new ArrayList<>();
				valueList.add(entry.getKey());
				count[entry.getValue()] = valueList;
			} else {
				List<Integer> valueList = count[entry.getValue()];
				valueList.add(entry.getKey());
			}
		}

		List<Integer> answer = new ArrayList<>();

		for (int i = count.length - 1; i >= 0; i--) {
			if (answer.size() == k) break;
			if (count[i] == null) continue;

			for (int j = 0; j < count[i].size(); j++) {
				answer.add(count[i].get(j));
			}
		}

		return answer.stream()
					.mapToInt(i -> i)
					.toArray();
	}
}

해답

1. heap (최대힙)

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // O(1) time
        if (k == nums.length) {
            return nums;
        }
        
        // 1. build hash map : character and how often it appears
        // O(N) time
        Map<Integer, Integer> count = new HashMap();
        for (int n: nums) {
          count.put(n, count.getOrDefault(n, 0) + 1);
        }

        // 힙을 초기화한다.
        // 힙 내의 값들의 우선 순위는 출현 빈도가 적은 문자열일수록 빨리 poll된다.
        Queue<Integer> heap = new PriorityQueue<>(
            (n1, n2) -> count.get(n1) - count.get(n2));

        // 2. heap의 개수가 k개가 유지되도록 한다.
        // 우선 heap에 key를 밀어넣고,heap의 사이즈가 k보다 클 경우 heap에서 poll 한다.
        // 이 때, poll되는 대상은 출현 빈도수가 적을수록 우선순위가 높다.
        // O(N log k) < O(N log N) time
        for (int n: count.keySet()) {
          heap.add(n);
          if (heap.size() > k) heap.poll();    
        }

        // 3. heap에 남아 있는 key들을 k개 만큼 뽑아낸다.
        // O(k log k) time
        int[] top = new int[k];
        for(int i = k - 1; i >= 0; --i) {
            top[i] = heap.poll();
        }
        return top;
    }
}

2. QuickSelection

• 설명을 봐도 잘 모르겠음. 추후에 다시 공부