“This is the 10th day of my participation in the Gwen Challenge in November. Check out the details: The Last Gwen Challenge in 2021.”

[B] [C] [D]

Given an integer array nums and an integer k, return the element with the highest frequency k. You can return the answers in any order.

Example 1:

Input: nums = [1,1,1,2, 3], k = 2 output: [1,2]Copy the code

Example 2:

Input: nums = [1], k = 1Copy the code

Tip:

  • 1 <= nums.length <= 105
  • kThe value range of is[1, the number of different elements in the array]
  • The question data is guaranteed to be unique, in other words, first in the arraykThe set of the high frequency elements is unique

Advanced: The time complexity of the algorithm you design must be better than O(n log n), where n ** is the array size.

The problem is to find the first k high frequency elements, usually maintain the first K maximum value of the problem, can be solved by the heap

The nature of the heap

Heap of insert

To insert a heap is to insert elements at the end of an array

It then determines whether the newly inserted element affects the balance of the current triplet. In the case of the large top heap, if the value of the inserted element is greater than the value of the root node, the two nodes are swapped until the triad of the newly inserted element is such that the root node has the maximum value of the current triad

Heap the pop-up

The eject operation is to eject the top element of the heap, corresponding to the element with subscript 0, update the end element to the first element of the array, and delete the previous end element

It then determines whether the new heaptop element affects the balance of the current triplet. In the case of the big top heap, if the new heap top element is not the current triplet maximum, it is swapped with the current triplet maximum until it becomes the maximum of the new triplet

Answer key 1

Now that we understand the properties of the heap, let’s look at the first solution to this problem

  1. usemapMaintains the values of the elements in the array and the number of occurrences
  2. Create a small top heap for maintenancekFour high frequency elements
  3. traversemap, if the elements in the heap are greater than or equal tok, and the top element of the heap is greater than the data in the loopvalValue, do not insert, otherwise the loop data is inserted into the heap
  4. When the heap is not empty, pop the top element of the heap and pop the value ofkeyPut it in the result array and return the result array

The code is as follows:

class MinHeap { constructor(max){ this.arr = []; this.size = 0; this.max = max; } // Insert element push(val){this.arr.push(val); this.size++; if(this.size>1){ let cur = this.size-1, parentInd = (cur-1)>>1; while(cur>0 && this.arr[parentInd].val>this.arr[cur].val){ [this.arr[parentInd],this.arr[cur]] = [this.arr[cur],this.arr[parentInd]] cur = parentInd; parentInd = (cur-1)>>1; } } while(this.size>this.max) this.pop(); } // pop(){if(this.empty()) return false; const res = this.arr[0] this.arr[0] = this.arr.pop(); this.size--; let cur = 0, childl = 1, childr = 2; while( (childl<this.size&&this.arr[childl].val<this.arr[cur].val) || (childr<this.size&&this.arr[childr].val<this.arr[cur].val) ){ if(childr<this.size&&this.arr[childr].val<this.arr[childl].val){ [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; {return this.size === 0} top(){return this.arr[0]}} var topKFrequent = function(nums, 1){return this.arr[0]} K) {// map maintains the values in the array and the number of occurrences const map = new map (); for(let i = 0; i<nums.length; I ++){const cur = nums[I] if(map.has(cur)){map.set(cur,map.get(cur)+1)}else{map.set(cur,1)}} // Create a small top heap for the first k elements const heap = new MinHeap(k); Map. ForEach ((val, key) = > {the if (heap. Size < k | | heap. The top (). Val < val) {heap. Push ({val, key})}}) / / put the heap element in the result array const ret = []; while(! heap.empty()){ ret.push(heap.pop().key) } return ret; };Copy the code

Answer key 2

  1. usemapMaintains the values of the elements in the array and the number of occurrences
  2. throughArray.from 将 mapConverted to an array
  3. Sort elements in descending order by the number of occurrences
  4. Put the values of the first K high frequency elements into the result array

The code is as follows:

Var topKFrequent = function(nums, k) {const map = new map (); for(let i = 0; i<nums.length; I ++){const cur = nums[I] if(map.has(cur)){map.set(cur,map.get(cur)+1)}else{map.set(cur,1)}} // Convert map to array const arr = Array.from(map); Arr.sort ((a,b) => b[1]-a[1]) const ret = []; for(let i = 0; i<k; i++){ ret.push(arr[i][0]) } return ret; };Copy the code

At this point, we have completed leetcode-347-first K high frequency elements in two ways

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