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