[B] [C] [D]

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

Note:

  1. Assume thatkIs always valid, 1 ≤k≤ Number of set elements.
  2. The words you enter are all lowercase letters.

Extended exercises:

  1. Try toO(n log k) time complexity andO(n) space complexity solution.

The sort order

The simplest and direct way in this paper is to count the words and their frequency of occurrence, and then sort each element in order of occurrence from largest to smallest, or alphabetically if the occurrence is the same

Finally, get the first k words of the descending sorted array

The code is as follows:

Var topKFrequent = function(words, k) {const map = new map (); for(let i = 0; i<words.length; i++){ const item = words[i]; If (map.has(item)){map.set(item,map.get(item)+1)}else{map.set(item,1)}} const arr = []; Map. ForEach ((val, name) = > {arr. Push ({name, val})}) / / to sort an array arr. Sort ((a, b) = > {the if (Dr. Al = = = b.v al) return A.name <b.name?-1:1 else return b.val-a.val}) const res = []; for(let i = 0; i<arr.length; i++){ if(res.length<k) res.push(arr[i].name) else break; } return res; };Copy the code

Small cap pile

Any problem that involves maintaining the first k maximum values can be solved by using a heap. In this case, we need to get the first K high frequency words, so we can maintain the first K high frequency words by using a small top heap and putting each group of words and their number into the heap at a time, Finally the heap before maintenance is the most commonly k high frequency words Then put the heap element in turn pop-up in the result array Because it is a little heap, so the pile top is a former k words appear in the frequency of at least a, so finally the pop-up roof when insert the result array element should be inserted into the result array in the head.

The code is as follows:

Constructor (k){constructor(k){this.arr = []; // Number of elements this.size = 0; This. Max = k; } // Insert element push(item){this.arr.push(item); this.size++; If (this.size>1){let cur = this.size-1, parent = (cur-1)>>1; while(cur>0&&compare(this.arr[parent],this.arr[cur])){ [this.arr[parent],this.arr[cur]] = [this.arr[cur],this.arr[parent]] cur = parent,parent = (cur-1)>>1; If (this.size>this.max) this.pop(); } pop(){if(this.size===1){this.size= 0; return this.arr.pop(); } // Pop the last element of the heap const res = this.arr[0]; this.arr[0] = this.arr.pop(); this.size--; // let cur = 0, childl = 1,childr = 2; while( (childl<this.size&&compare(this.arr[cur],this.arr[childl])) || (childr<this.size&&compare(this.arr[cur],this.arr[childr])) ){ if(childr<this.size&&compare(this.arr[childl],this.arr[childr])){ [this.arr[cur],this.arr[childr]] = [this.arr[childr],this.arr[cur]] cur = childr }else{ [this.arr[cur],this.arr[childl]] = [this.arr[childl],this.arr[cur]]  cur = childl } childl = cur*2+1,childr = cur*2+2 } return res; } top(){return this.arr[0]}} function compare(item1,item2){ Val ===item2.val) return item2.name>item1.name // Otherwise order item2.val<item1.val} var topKFrequent Const map = new map ();} function(words, k) {const map = new map (); for(let i = 0; i<words.length; i++){ const item = words[i]; If (map.has(item)){map.set(item,map.get(item)+1)}else{map.set(item,1)}} // Create a small top heap instance const heap = new MinHeap(k); ForEach ((val,name) => {const item = {name,val} // If the number of elements in the heap is less than K or the current element is larger than the top element of the heap, Then insert the if (heap size < k | | compare (item, heap. Top ())) {heap. Push (item)}}) / / popup in the heap element, in the result array const res = []; while(heap.size){ res.unshift(heap.pop().name) } return res; };Copy the code

At this point we are done with leetcode- 692-the first K high frequency words

If you have any questions or suggestions, please leave a comment!