Leetcode
2020.04.14 07:09

# 347. Top K Frequent Elements

조회 수 102 추천 수 0 댓글 0
?

#### 단축키

Prev이전 문서

Next다음 문서

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

#### 단축키

Prev이전 문서

Next다음 문서

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

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;
}
}```

?

 제목+내용제목내용댓글이름닉네임아이디태그
List of Articles
번호 분류 제목 글쓴이 날짜 조회 수
17 Leetcode 287. Find the Duplicate Number 2020.04.16 126
16 Leetcode 253. Meeting Rooms II 2020.04.15 104
15 Leetcode 731. My Calendar II 2020.04.15 100
14 Leetcode 729. My Calendar I 2020.04.15 104
13 Leetcode 692. Top K Frequent Words 2020.04.15 93
12 Leetcode 973. K Closest Points to Origin 2020.04.15 107
11 Leetcode 75. Sort Colors 2020.04.14 101
10 Leetcode 2. Add Two Numbers 2020.04.14 96
9 Leetcode 23. Merge k Sorted Lists 2020.04.14 104
» Leetcode 347. Top K Frequent Elements 2020.04.14 102
7 Leetcode 994. Rotting Oranges 2020.04.14 115
6 Leetcode 3. Longest Substring Without Repeating Characters 2020.04.09 113
5 Leetcode 62. Unique Paths 2020.04.09 105
4 Leetcode 946. Validate Stack Sequences 2020.04.08 107
3 Leetcode 114. Flatten Binary Tree to Linked List 2020.04.06 117
2 Leetcode 430. Flatten a Multilevel Doubly Linked List 2020.04.06 104
1 Leetcode 1055. Shortest Way to Form String 2020.04.06 125
Board Pagination Prev 1 2 3 4 Next
/ 4