[LeetCode] 347. Top K Frequent Elements (C++)

문제

https://leetcode.com/problems/top-k-frequent-elements/description/

Top K Frequent Elements - LeetCode

 

 

풀이

 

난이도: 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)이다.

 

 

코드