ARTS Week 28

Algorithm

This week’s LeetCode problem is 347. Top K Frequent Elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

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

First traverse the array once, and use Map to count the occurrences of each element. Then use the occurrences of different elements as the basis for sorting, maintain a small top heap of size k, and finally get the elements at the top of the heap.

import java.util.SortedMap;
class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> numCount = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            numCount.put(nums[i], numCount.getOrDefault(nums[i], 0) + 1);
        }
        PriorityQueue<int[]> pq = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        for (int key : numCount.keySet()) {
            int count = numCount.get(key);
            if (pq.size() == k) {
                if (pq.peek()[1] < count) {
                    pq.poll();
                    pq.offer(new int[]{key, count});
                }
            } else {
                pq.offer(new int[]{key, count});
            }
        }
        int[] ans = new int[k];
        for (int i = 0; i < k; i++) {
            ans[i] = pq.poll()[0];
        }
        return ans;
    }
}

Review

This week’s Review is for the following article: Why don’t I have a blog?

The author mainly introduces the reasons why he does not open a blog. Although the author likes coding and reading, he still does not open a blog. He mainly lists the following reasons:

• “I don’t have anything interesting to say”: the author doesn’t think he has too many strong, unique, novel ideas to share.
• “I’m not a good programmer”: the author believes that most of his skills are just beginner level and there is no need to share them.
• “I don’t think it’s good CV building”: The author thinks that the average blog is not enough as a good resume building platform, if you only have a blog, maybe no one will visit.

Tip

In Makefile, a .PHONY can be used to set a pseudo target to realize other functions, such as the function of make clean. The sample code is as follows:

.PHONY : clean
clean:
         rm $(OBJS) *.o a.out

Share

My state of this week is not very good. It feels like it is in a low ebb. I am not interested in doing many things, and the efficiency is not high. I need to adjust my state, find the root reason, and come on :)