728x90
반응형
LeetCode-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.
note : time complexity must be better than O(n log n), where n is the array s size.
Over *
:::python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
if len(set(nums))==1:
return [nums[0]]
answer = []
count = collections.Counter(nums).most_common(n=k)
return [i[0] for i in count]
Result : 111ms Memory: 21mb
Top K Frequent Elements
Top K Frequent Elements는 정수 배열에서 가장 빈번하게 등장하는 상위 K개의 원소를 찾는 알고리즘입니다.
예를 들어, [1,1,1,2,2,3]에서 상위 2개의 원소를 찾는다면, 1과 2가 선택됩니다. 1은 3번, 2는 2번 등장하였기 때문입니다.
이 알고리즘은 hash table과 heap을 이용하여 구현할 수 있습니다.
- hash table
- 정수 배열을 순회하며 원소의 등장 횟수를 저장하는 hash table을 생성합니다.
- 접근 횟수가 많은 상위 K개의 원소를 저장할 결과 배열을 생성합니다.
- hash table에서 가장 등장한 횟수가 큰 원소부터 K개 까지만 결과 배열에 저장합니다.
- heap
- 정수 배열을 순회하며 원소의 등장 횟수를 저장하는 hash table을 생성합니다.
- hash table을 바탕으로 heap을 생성합니다. heap에는 원소의 등장 횟수를 저장합니다.
- heap에서 상위 K개의 원소를 pop하여 결과 배열에 저장합니다.
이 알고리즘의 시간복잡도는 정수 배열을 순회하는 O(n)과 hash table 또는 heap을 사용하여 원소를 추출하는 O(K log K)입니다. 따라서 전체 시간복잡도는 O(n + K log K)입니다.
위 알고리즘은 빅데이터 분석에서 비즈니스적인 인사이트를 도출하는 등 매우 중요한 역할을 합니다.
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
# Create a hash table to store the frequency of each element
freq = {}
for num in nums:
if num in freq:
freq[num] += 1
else:
freq[num] = 1
# Sort the hash table by frequency in descending order
freq = {k: v for k, v in sorted(freq.items(), key=lambda item: item[1], reverse=True)}
# Select the k elements with the highest frequency
result = []
i = 0
for num, count in freq.items():
result.append(num)
i += 1
if i == k:
break
return result
반응형
'One step' 카테고리의 다른 글
[leetcode-38] Count and Say (0) | 2023.05.05 |
---|---|
[leetcode-48] Rotate Image (0) | 2023.04.30 |
[leetcode-43] Multiply Strings (0) | 2023.04.26 |
[leetcode-14] Longest Common Prefix (0) | 2023.04.24 |
[leetcode-12] Integer to Roman (0) | 2023.04.21 |