Shulou(Shulou.com)06/01 Report--

This article mainly explains "how to use heap and map". The explanation in this article is simple and clear, easy to learn and understand. Please follow the ideas of Xiaobian and go deep into it slowly to study and learn "how to use heap and map" together.

The Top K question is a very common algorithm question in interviews.

Leetcode is the same as Leetcode. Here is the example of Leetcode.

Title:

Give a group of words and count the k words with the highest frequency.

For example,"I love leetcode, I love coding" is the highest frequency of the two I and love.

Some students think this question is very simple, but in fact this question is only the mother question, it can be upgraded to the system design level to ask:

The most k goods sold on an e-commerce website in the past hour.

Let's look at the algorithm level first:

Thinking:

Count the frequency of all the words, and then sort them by frequency to pick the top k.

Details:

Use HashMap to store the frequency of words, minHeap/maxHeap to get the first k.

Achieve:

Create a HashMap, traverse the entire array, and correspondingly add the number of occurrences of this word + 1.

Time complexity is O(n).

Use minHeap of size = k to store the results, and define the comparison order specified in the question.

a. First, sort by frequency of occurrence;

b. In alphabetical order when frequencies are the same.

Go through this map if

a. minHeap is added when the number of words in minHeap is less than k;

b. Or replace words with higher frequencies.

Space-time complexity analysis:

The first step is O(n) and the third step is nlog(k), so the total time complexity is O(nlog k).

With an extra heap and map, the space complexity is O(n).

Code:

class Solution { public List topKFrequent(String[] words, int k) { // Step 1 Map map = new HashMap(); for (String word : words) { Integer count = map.getOrDefault(word, 0); count++; map.put(word, count); } // Step 2 PriorityQueue minHeap = new PriorityQueue(k+1, new Comparator() { @Override public int compare(Map.Entry e1, Map.Entry e2) { if(e1.getValue() == e2.getValue()) { return e2.getKey().compareTo(e1.getKey()); } return e1.getValue().compareTo(e2.getValue()); } }); // Step 3 List res = new ArrayList(); for(Map.Entry entry : map.entrySet()) { minHeap.offer(entry); if(minHeap.size() > k) { minHeap.poll(); } } while(! minHeap.isEmpty()) { res.add(minHeap.poll().getKey()); } Collections.reverse(res); return res; }} Thank you for reading, the above is "how to use heap and map" content, after the study of this article, I believe that everyone on how to use heap and map this problem has a deeper experience, the specific use of the situation also needs to be verified by practice. Here is, Xiaobian will push more articles related to knowledge points for everyone, welcome to pay attention!

Welcome to subscribe "Shulou Technology Information " to get latest news, interesting things and hot topics in the IT industry, and controls the hottest and latest Internet news, technology news and IT industry trends.