Leetcode

# 347. Top K Frequent Elements

by hooni posted Apr 14, 2020
?

#### 단축키

Prev이전 문서

Next다음 문서

ESC닫기

크게 작게 위로 아래로 댓글로 가기 인쇄

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

```Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
```

Example 2:

```Input: nums = [1], k = 1
Output: [1]```

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.

```class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
List<Integer> result = new ArrayList<Integer>();
int topK = 0;

for(int i=0; i<nums.length; i++){
if(hmap.containsKey(nums[i])){
hmap.put(nums[i], hmap.get(nums[i])+1);
}else{
hmap.put(nums[i], 1);
}
}

for(int i=0; i<k; i++){
int maxKey = 0;
int maxValue = 0;
/*
// Getting a Set of Key-value pairs
Set entrySet = hmap.entrySet();
Iterator it = entrySet.iterator();
while(it.hasNext()){
Map.Entry item = (Map.Entry)it.next();
int value = (int)item.getValue();
if(value > maxValue){
maxKey = (int)item.getKey();
maxValue = value;
}
}
*/
for(Map.Entry item : hmap.entrySet()){
int value = (int)item.getValue();
if(value > maxValue){
maxKey = (int)item.getKey();
maxValue = value;
}
}

//hmap.put(maxKey, -1);
hmap.remove(maxKey);
}

return result;
}
}```

```class Solution {
public List<Integer> topKFrequent(int[] nums, int k) {
//count the frequency for each element
HashMap<Integer, Integer> hmap = new HashMap<>();

for(int num : nums){
hmap.put(num, hmap.getOrDefault(num, 0) + 1);
}

// create a min heap
PriorityQueue<Map.Entry<Integer, Integer>> queue
= new PriorityQueue<>(Comparator.comparing(e -> e.getValue()));

//maintain a heap of size k.
for(Map.Entry<Integer, Integer> item : hmap.entrySet()){
queue.offer(item);
if(queue.size() > k){
queue.poll();
}
}

//get all elements from the heap
List<Integer> result = new ArrayList<>();
//while(!queue.isEmpty()){
while(queue.size() > 0){
}

//reverse the order
Collections.reverse(result);

return result;
}
}```

1 2 3 4