This is the 12th day of my participation in the More text Challenge. For details, see more text Challenge

The first K high-frequency words (Question No. 682)

The title

Given a non-empty list of words, return the top K words with the most occurrences.

The answers should be returned in descending order of word occurrence. 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" comes before "love" in alphabetical order.Copy the code

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", "day"] ["the", "is", "sunny", "day"] ["the", "is", "day"]Copy the code

Note:

  • Assume thatkIs always valid value,1 ≤ K ≤ number of set elements.
  • The input word consists of lowercase letters.

Extended exercises:

Try to solve in order (n log K) time complexity and order (n) space complexity.

link

Leetcode-cn.com/problems/to…

explain

This one. This one was easier than I thought.

I thought the medium questions were a little easy, but I didn’t. I felt that I could be classified as the simple ones.

First look at the problem, you have already thought of the solution, as long as you get the number of occurrences of each word, and then sort it, there is no difficulty.

But is that really all?

After reading the answer, I found that the first k or the last K elements can be solved by using a priority queue. The principle of the priority queue is very simple.

First, determine the final length, which is usually given as a parameter.

If the length of the array exceeds k, then remove the elements at the end of the array and proceed to the next insertion operation.

So you get the final result after all the elements are inserted.

I didn’t think of such a solution at the time, just a regular one.

By the way, the premise here is that you can compare the order of letters using the localeCompare() method of strings.

Your own answer (conventional solution)

Their own answer is ugly, more code.

var topKFrequent = function(words, k) {
  var obj = {}
      arr = []
  for (const word of words) {
    if (obj[word]) {
      obj[word]++
    } else {
      obj[word] = 1
      arr.push(word)
    }
  }
  arr.sort((a, b) => {
    if (obj[a] === obj[b]) return a.localeCompare(b)
    return obj[b] - obj[a]
  })
  return arr.slice(0, k)
};
Copy the code

It’s very simple logic, first we loop through the array, get an object and an array. The object stores the number of occurrences of each word, and the array can be understood as an array of original words after deduplicated.

If you look closely, you’ll see that the deduplicated array doesn’t need to exist at all. You can use object.keys (obj) to get it, and the separate slice() is not necessary; it can be followed by sort().

So this code can be simplified as 👇 :

var topKFrequent = function(words, k) {
  var obj = {}
  for (const word of words) {
    obj[word] = (obj[word] || 0) + 1
  }
  return Object.keys(obj)
    .sort((a, b) => obj[a] === obj[b] ? a.localeCompare(b) : obj[b] - obj[a])
    .slice(0, k)
};
Copy the code

That looks pretty neat, right, but there’s actually simpler code, and I’ll talk about that later.

Better approach (priority queue)

The logic of the priority queue is explained in the explanation section and will not be explained here.

The author looked through the answers and found no JavaScript solution to the priority queue, nor did the official JavaScript answer be provided. The following solution is written by the author himself, if there is a problem, please point out in time.

var topKFrequent = function(words, k) {
  var map = new Map()
      arr = []
  function sortArr(a, b) {
    return map.get(a) === map.get(b) ? a.localeCompare(b) : map.get(b) - map.get(a)
  }
  for (const word of words) {
    map.set(word, map.get(word) ? map.get(word) + 1 : 1)
  }
  for (const word of map.keys()) {
    arr.push(word)
    arr.sort(sortArr)
    if (arr.length > k) arr.pop()
  }
  return arr
};
Copy the code

SortArr is a function used to sort the array, then the old way to get the number of occurrences of each word, and finally maintain a priority queue, very simple code.

Better method (conventional solution – one line)

This is one of the more interesting methods that I have seen. No additional objects are added. It is really a single line of code.

var topKFrequent = function(words, k) {
  return [...words.reduce((map, word) => map.set(word, (map.get(word) || 0) + 1), new Map)]
    .sort((a, b) => a[1] === b[1] ? a[0].localeCompare(b[0]) : b[1] - a[1])
    .slice(0, k)
    .map(v => v[0])
};
Copy the code

It might look a little convoluting at first, but let’s open it up here.

First look inside [] 👇 :

words.reduce((map, word) => map.set(word, (map.get(word) || 0) + 1), new Map)
Copy the code

Here we use a reduce, the final return value is a Map object, I believe you can understand this step, then expand this object will get what? The result is a two-dimensional array 👇 :

[
	['the', 4],
	['is', 2],
	...
]
Copy the code

The first element of the subarray is the Map key, and the second element is the value.

After we get the array we want, we start sort, and use slice() to get the first K elements of the array.

And then we just take the first element of the subarray.

In fact, I do not recommend a one-line solution, but this answer is very interesting and easy to understand, recommended.




PS: To view past articles and titles, click on the link below:

Here’s 👇 by date

Front Brush path – Directory (Date classification)

After some friends remind, the feeling should also be classified according to the type of questions here is in accordance with the type of 👇

Front brush problem path – Catalogue (Question type classification)

Those who are interested can also check out my personal homepage 👇

Here is RZ