This article is participating in the “Java Theme Month – Java Brush questions punch card”, see the activity link for details

Topic describes

Given a non-empty list of words, return the first k occurrences of the most common words.

The answers returned should be sorted in order of word frequency. If different words have the same frequency, sort them alphabetically.

Example 1:

Input:"i"."love"."leetcode"."i"."love"."coding"], k = 2Output:"i"."love"] resolution:"i" 和 "love"Are the two words that appear most frequently, and both are2Times. Notice, alphabetically"i" 在 "love"Before.Copy the code

Example 2:

Input:"the"."day"."is"."sunny"."the"."the"."the"."sunny"."is"."is"], k = 4Output:"the"."is"."sunny"."day"] resolution:"the"."is"."sunny" 和 "day"Are the four words that appear most frequently, and the frequency of occurrence is4.3.2 和 1Times.Copy the code

Note:

Assuming k is always valid, 1 ≤ k ≤ the number of set elements.

The words you enter are all lowercase letters.

Thought analysis

The general idea is divided into three steps

1. Use map to count the number of words.

2. Then we put the word and its number into an object Entry.

3. Finally, we sort all the object entries. The sorting rule is that the words with a large number should be ranked first, and those with the same number can be sorted in dictionary order.

AC code

class Solution {
    public List<String> topKFrequent(String[] words, int k) {
        HashMap<String, Integer> map = new HashMap<>();
        for (String word : words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        TreeSet<Entry> set = new TreeSet<>();
        map.forEach((word, count) -> {
            Entry entry = new Entry();
            entry.word = word;
            entry.count = count;
            set.add(entry);
        });
        List<String> answer = new ArrayList<>(k);
        for (Entry entry : set) {
            if (answer.size() == k) {
                break;
            }
            answer.add(entry.word);
        }
        return answer;
    }

    private static class Entry implements Comparable<Entry> {
        String word;
        int count;

        @Override
        public int compareTo(Entry o) {
            if (this.count == o.count) {
                return this.word.compareTo(o.word);
            }
            return o.count - this.count; }}}Copy the code

conclusion

Train of thought is the most important, before solving the problem, we need to draw up a good train of thought. It is better to draw a flow chart on the draft to know how to write the code.