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 :)

--

--

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store