1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
|
"""
Question
Top K Elements in List
Medium
Given an integer array nums and an integer k, return the k most frequent elements within the array.
The test cases are generated such that the answer is always unique.
You may return the output in any order.
Example 1:
Input: nums = [1,2,2,3,3,3], k = 2
Output: [2,3]
Example 2:
Input: nums = [7,7], k = 1
Output: [7]
Constraints:
1 <= nums.length <= 10^4.
-1000 <= nums[i] <= 1000
1 <= k <= number of distinct elements in nums.
"""
from typing import Dict, List, Tuple
class Solution:
"""
A class to solve top_k_elements from hash
"""
def hashmap(self, nums: List[int], k: int) -> List[int]:
"""
Frequent elements from the input nums: List[int] and k: int using a hashmap approach.
Args:
nums: List[int]: integer list
k: int: frequency
Returns:
List[int]: elements list
"""
count: Dict = {}
freq: List = [[] for _ in range(len(nums) + 1)]
for n in nums:
count[n] = 1 + count.get(n, 0)
for i, c in count.items():
freq[c].append(i)
res: List = []
for i in range(len(freq) - 1, 0, -1):
for j in freq[i]:
res.append(j)
if len(res) == k:
return res
return []
def print(self, examples: Dict[str, Tuple[List[int], int]]) -> None:
"""
funciton to print the result.
Args:
example: Dict, a dictionary of examples
"""
for name, (param1, param2) in examples.items():
result = self.hashmap(param1, param2)
print(f"{name}: {result}")
def main(self):
"""
main function to call print function to test examples
"""
cases = {"case1": ([1, 2, 2, 3, 3, 3], 2), "case2": ([7, 7], 2)}
self.print(cases)
solution = Solution()
solution.main()
"""
Solution
url: https://neetcode.io/problems/top-k-elements-in-list
video: https://youtu.be/YPTqKIgVk-k
1. Bucket sort
time: O(n)
space: O(n)
code:
```python
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
count = {}
freq = [[] for i in range(len(nums) + 1)]
for n in nums:
count[n] = 1 + count.get(n, 0)
for n, c in count.items():
freq[c].append(n)
res = []
for i in range(len(freq) - 1, 0, -1):
for n in freq[i]:
res.append(n)
if len(res) == k:
return res
```
2. Heap sort (max heap)
time: O(k*logn)
space: O(k*logn)
3. Sorting
time: O(n*logn)
space: O(n*logn)
"""
|
