[LeetCode] 347. Top K Frequent Elements (C++)
문제
https://leetcode.com/problems/top-k-frequent-elements/description/
Top K Frequent Elements - LeetCode
Can you solve this real interview question? 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. Example 1: Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
leetcode.com
풀이
난이도: Medium
숫자 배열에서 가장 많이 등장하는 수 K번째까지를 구하는 문제.
숫자 배열의 길이는 100,000 개이기 때문에 정렬해서 푼다면 O(n log n)의 복잡도로도 해결가능하다.
하지만, 문제의 하단에 추가적인 도전과제가 있다.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
따라서 O(n log n) 보다는 잘해보자.
숫자의 범위는 -10,000 ~ +10,000이다. 이는 n(100,000)의 5분의 1 수준으로 이를 m라고 하자.
따라서 삽입과 찾기에 O(1)의 복잡도를 가지는 unordered_map<등장 숫자, 카운트>을 사용해서 배열에 등장하는 수를 카운트해 보자.
unordered_map에 모든 숫자 배열을 확인하면서 카운트하는 복잡도는 O(n)이다.
unordered_map에는 최대 m개의 key가 존재하게 된다.
이제 unordered_map의 모든 <등장 숫자, 카운트>데이터를 우선순위 큐에 삽입하자.
모든 데이터를 우선순위 큐에 삽입하는 복잡도는 O(m log m)이다.
이때 카운트의 내림차순으로 저장시키자.
이제 우선순위 큐에서 k개를 pop 하면, 가장 많이 등장하는 수 k번째까지 구할 수 있다.
우선순위 큐에서 삭제하는 복잡도는 O(log k)이다.
최종적으로 시간 복잡도는 O(n + m log m + k) = O(m log m)이다.
m은 n의 1/5 크기이기 때문에 O(m log m) < O(n log n)이다.
코드