[LeetCode] 347. Top K Frequent Elements
LeetCode 347번 문제를 풀어보았다.. Link
Problem
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Intuition
주어진 배열안에 숫자들이 몇개씩 있는지 확인하고, 가장 빈도가 높은 k개의 요소를 반환해야하는 문제.
숫자가 몇개있는지 확인 –> Dictionary가 바로 생각났다.
각 요소가 몇개씩 있는지 기록하고, 이를 내림차순으로 정렬하고 k개를 반환하면 된다.
Approach
- 각 요소별 빈도가 기록되는
num_dic을 생성한다. f_list에 요소의 종류와 그 빈도로 구성된 1D list를 append한다.- f_list를 빈도를 기준으로 Sorting한다.
- Sorting을 오름차순으로 했기 때문에 뒤에서 부터 k개를 append한다.
Complexity
Time complexity:
nums성분의 개수를n이라고 할 때, \(O(n) + O(n log n) = O(n log n)\)이다. Worst case에선 \(O(n log n)\)이 된다.Space complexity: \(O(n)\)
My Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
num_dic = {}
for num in nums:
if num in num_dic:
num_dic[num] += 1
else:
num_dic[num] = 1
f_list = []
for key in num_dic:
f_list.append([num_dic[key], key])
f = sorted(f_list)
answer = []
for i in range(len(f)-1, len(f)-k-1, -1):
answer.append(f[i][1])
return answer
시간복잡도를 더 줄이려면 어떻게 해야할까?
Sorting이 Bottleneck이 되기 때문에 Sorting없이 줄일 방법을 생각해야한다.
위 코드는 현재 빈 리스트 f_list에 반복되는 요소와 그 빈도수를 하나의 1D List로 만들어 추가하고 있다.
이렇게 하지말고 만약 마치 DP처럼 빈도수를 Index를 사용하고 해당 빈도수를 가지는 요소들을 append시켜 저장한다면 어떨까?
Sorting을 하지않고 List에 f_list의 각 요소를 Append하는 것이기 때문에 시간복잡도는 \(O(n)\)이 된다.
이를 코드로 옮겨보자.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
num_dic = {}
for num in nums:
if num in num_dic:
num_dic[num] += 1
else:
num_dic[num] = 1
# 0의 빈도수는 없고, 최대로 많은 빈도를 가져봐야 len(nums)보다 적거나 같음
f_list = [[] for i in range(len(nums)+1)]
for num, f in num_dic.items():
f_list[f].append(num)
#f = sorted(f_list)
answer = []
for i in range(len(f_list)-1, 0, -1):
for num in f_list[i]:
answer.append(num)
if len(answer) == k:
return answer
NeetCode님 감사합니다.