Title source: Leetcode692
The title
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 = 2 output: [” I “, “love”] resolution: “I” and “love” as the two largest occurrences of words that are 2 times. Notice that “I” precedes “love” alphabetically.
Example 2:
Input: [” the “, “day” and “is”, “sunny”, “the”, “the”, “the”, “sunny”, “is” and “is”], k = 4 output: [” The “, “is”, “sunny”, “day”] [“the”, “is”, “sunny” and “day”] [“the”, “is”, “sunny” and “day”]
Note:
Assuming k is always valid, 1 ≤ k ≤ the number of set elements. The words you enter are all lowercase letters.
Analysis of the
- Start by collecting the number of occurrences of each word
n
- According to the question, when the word appears the same number of times, then we can pass
localeCompare
Method to sort localeCompare
The results are as follows:
- Finally according to the sorting results before taking
k
a
Pseudo code
- To define a
map
Variables are used to store each word and its occurrence relationship - traverse
words
Through theset
Method stored tomap
Is required at this timeget
Method gets the current count and +1. If it does not get the count, the word appears for the first time - through
from
Method will bemap
Objects are converted to arrays for easy traversal - through
sort
Method to sort, when the first letter of the word is not the same is sorted according to the number of times, the same can passlocaleCompare
Gets the alphabetical sorting result - through
slice
The firstk
a - Finally, an array of words is returned
Code implementation
/**
* @param {string[]} words
* @param {number} k
* @return {string[]}
*/
var topKFrequent = function(words, k) {
let map = new Map()
for(let word of words){
map.set(word,(map.get(word)||0)+1)
}
let arr = Array.from(map)
arr.sort((a,b) => b[1] === a[1] ? a[0].localeCompare(b[0]) : b[1]-a[1])
let top = arr.slice(0,k)
return top.map(a => a[0])
};
Copy the code