Top K Frequent Elements – LeetCode Solution Java , Python 3, Python 2 , C , C++, Best and Optimal Solutions , All you need.
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]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Constraints:
1 <= nums.length <= 105
-104 <= nums[i] <= 104
k
is in the range[1, the number of unique elements in the array]
.- It is guaranteed that the answer is unique.
C++ Top K Frequent Elements LeetCode Solution
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}
vector<int> res;
// pair<first, second>: first is frequency, second is number
priority_queue<pair<int,int>> pq;
for(auto it = map.begin(); it != map.end(); it++){
pq.push(make_pair(it->second, it->first));
if(pq.size() > (int)map.size() - k){
res.push_back(pq.top().second);
pq.pop();
}
}
return res;
}
};
Java Top K Frequent Elements LeetCode Solution
// use an array to save numbers into different bucket whose index is the frequency
public class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
Map<Integer, Integer> map = new HashMap<>();
for(int n: nums){
map.put(n, map.getOrDefault(n,0)+1);
}
// corner case: if there is only one number in nums, we need the bucket has index 1.
List<Integer>[] bucket = new List[nums.length+1];
for(int n:map.keySet()){
int freq = map.get(n);
if(bucket[freq]==null)
bucket[freq] = new LinkedList<>();
bucket[freq].add(n);
}
List<Integer> res = new LinkedList<>();
for(int i=bucket.length-1; i>0 && k>0; --i){
if(bucket[i]!=null){
List<Integer> list = bucket[i];
res.addAll(list);
k-= list.size();
}
}
return res;
}
}
Python 3 Top K Frequent Elements LeetCode Solution
class Solution(object):
def topKFrequent(self, nums, k):
hs = {}
frq = {}
for i in xrange(0, len(nums)):
if nums[i] not in hs:
hs[nums[i]] = 1
else:
hs[nums[i]] += 1
for z,v in hs.iteritems():
if v not in frq:
frq[v] = [z]
else:
frq[v].append(z)
arr = []
for x in xrange(len(nums), 0, -1):
if x in frq:
for i in frq[x]:
arr.append(i)
return [arr[x] for x in xrange(0, k)]
Array-1180
String-562
Hash Table-412
Dynamic Programming-390
Math-368
Sorting-264
Greedy-257
Depth-First Search-256
Database-215
Breadth-First Search-200
Tree-195
Binary Search-191
Matrix-176
Binary Tree-160
Two Pointers-151
Bit Manipulation-140
Stack-133
Heap (Priority Queue)-117
Design-116
Graph-108
Simulation-103
Prefix Sum-96
Backtracking-92
Counting-86
Sliding Window-73
Linked List-69
Union Find-66
Ordered Set-48
Monotonic Stack-47
Recursion-43
Trie-41
Binary Search Tree-40
Divide and Conquer-40
Enumeration-39
Bitmask-37
Queue-33
Memoization-32
Topological Sort-31
Geometry-30
Segment Tree-27
Game Theory-24
Hash Function-24
Binary Indexed Tree-21
Interactive-18
Data Stream-17
String Matching-17
Rolling Hash-17
Shortest Path-16
Number Theory-16
Combinatorics-15
Randomized-12
Monotonic Queue-9
Iterator-9
Merge Sort-9
Concurrency-9
Doubly-Linked List-8
Brainteaser-8
Probability and Statistics-7
Quickselect-7
Bucket Sort-6
Suffix Array-6
Minimum Spanning Tree-5
Counting Sort-5
Shell-4
Line Sweep-4
Reservoir Sampling-4
Eulerian Circuit-3
Radix Sort-3
Strongly Connected Componen-t2
Rejection Sampling-2
Biconnected Component-1
Leave a comment below