# Preface

Hello, I'm a long way from junior year to junior year. The direction is back-end and occasionally front-end. Now the main language is Java. Before a long time, I was learning some technology of web development, but I haven't done anything like data structure, algorithm and so on for a long time. I intend to pick it up and do a good job.

This period is also an opportunity to coincide with seeing the blog of Tsao Ha Road Flying, adding self-study groups, and happening to see the blogger organization organized a leetcode brushing and punching activities in the group. I also participated in this activity for a month, intending to insist on taking some time to do some topics every day, and record them through the blog.

There is currently a Github repository refresh Title (leetcode): Code Casual leetcode Title , currently stack and queue themes.

# subject

Title Source leetcode

leetcode address: 347. First K High Frequency Elements , difficulty: medium.

Title description (from leetcode):

```Give you an array of integers nums And an integer k ，Please return to the time before the frequency of occurrence k High elements. You can return the answers in any order.

Example 1:
input: nums = [1,1,1,2,2,3], k = 2
output: [1,2]

Example 2:
input: nums = , k = 1
output: 

Tips:
1 <= nums.length <= 105
k The range of values is [1, Number of different elements in the array]
Topic data guarantees that the answer is unique, in other words, first in the array k The set of high frequency elements is unique
```

Local debugging code:

```class Solution {

public int[] topKFrequent(int[] nums, int k) {
...
}

public static void main(String[] args) {
int[] nums = new int[]{1,1,1,2,2,3};
System.out.println(Arrays.toString(new Solution().topKFrequent(nums,2)));
}

}
```

# Problem

## NO1: Hash Table + Priority Queue

Idea: First use a hash table to count the frequency of corresponding values, and then create a priority queue to set up a small-to-large sorting comparator. After inserting a set of key s and values each time, determine if the current capacity is > K. If it is larger than the queue head directly (with the lowest frequency in the queue), the k-group data in the queue can be retrieved through the final traversal.

Code:

```public int[] topKFrequent(int[] nums, int k) {
//Use map to count the frequency of the specified number, key is num, value is frequency
Map<Integer,Integer> map = new HashMap<>();
for (int num : nums) {
map.put(num,map.getOrDefault(num,0)+1);
}
Set<Map.Entry<Integer, Integer>> entries = map.entrySet();
//Create a priority queue, pass in the Comparator anonymous interface class, insert elements into the queue from small to large
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((o1,o2)->o1.getValue()-o2.getValue());
for (Map.Entry<Integer, Integer> entry : entries) {
queue.offer(entry);
if(queue.size() > k){  //Once the number of queues is greater than k, the queue with the lowest frequency will be queued directly (queue head)
queue.poll();
}
}
//Finally, the corresponding maximum k value is taken out
int[] maxNums = new int[k];
for (int i = k-1; i >=0 ; i--) {
maxNums[i] = queue.poll().getKey();
}
return maxNums;
}
```

## NO2: Sort traversal + priority queue

Idea: Sort small to large first, then iterate through the entire array to [i]!=[i-1] as the basis for storage in the queue, the queues are sorted from large to small, each time after entering the queue to determine whether > k, if greater than the queue. The first k high frequency elements can be obtained by traversing K at last.

Code:

```public int[] topKFrequent(int[] nums, int k) {
Arrays.sort(nums);
//Priority queue, arranged from smallest to largest frequency (Comparator returns negative numbers from smallest to largest, if positive numbers from large to small)
PriorityQueue<int[]> queue = new PriorityQueue<int[]>((o1, o2) -> o1 - o2);
//Traversing an array
int i = 1;
int j = 1;
for (; i < nums.length; i++) {
if (nums[i] == nums[i - 1]) {
j++;
} else {
queue.offer(new int[]{nums[i - 1], j});
if (queue.size() > k) {  //Remove as soon as the number is greater than the original k
queue.poll();
}
j = 1;
}
}
queue.offer(new int[]{nums[i - 1], j});
if (queue.size() > k) {
queue.poll();
}
//Remove k from queue
int[] maxNums = new int[k];
for (int l = 0; l < k; l++) {
maxNums[l] = queue.poll();
}
return maxNums;
}
``` # Reference Article

. leetcode puzzle

I am a long way. Thank you for your patience in reading. If you have any questions, please point out that I will actively adopt them!
Welcome to my Public Number, Long Way Java, to share Java learning articles and related materials
Q Group: 851968786 We can discuss learning together
Note: Reprint is OK, you need to attach a link to the article

Keywords: Algorithm leetcode

Added by needphphelp on Fri, 12 Nov 2021 20:19:17 +0200