# 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 = [1], k = 1 output: [1] 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[1] - o2[1]); //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()[0]; } return maxNums; }

# Reference Article

[1]. leetcode puzzle

[2]. Code Casual Record - 347. Top K High Frequency Elements

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