1. Title Description

Finds the KTH largest element in the unsorted array. Note that you need to find the KTH largest element of the sorted array, not the KTH distinct element.

Example 1:

Input: [3, 2, 1, 5, 6, 4] and k = 2 Output: 5Copy the code

Example 2:

Input: [3, 2, 3, 1, 2, 4, 5, 5, 6] and k = 4 Output: 4Copy the code

Note: You can assume that k is always valid and that 1 ≤ k ≤ the length of the array.

Second, train of thought analysis

Simply get the value of k – 1 in a descending sorted array. The KTH largest element doesn’t need to be repeated, just sort it and get the KTH value.

AC code

The sorting

var findKthLargest = function(nums, k) { return nums.sort((a, b) => b - a)[k - 1] /** * const _nums = nums.sort((a, * / return _nums[k-1] // Returns the KTH largest element. * since the array starts at 0, we take the element of k-1 */}Copy the code

The minimum heap

/** * minimum heap * inserts values at the bottom of the heap, the end of the array. * then it moves up, swapping the value with its parent until the parent is less than or equal to the heap of the inserted value * of size K, The time complexity of the inserted element is O(logk) */ class MinHeap {constructor() {this.heap = [] // heap} /** * The inserted value * @param value The value to be inserted */ Insert (value) {this.heap.push(value) // Push the value to the end of the heap this.shiftUp(this.heap.length-1) // perform the shift method} /** * move up * @param index */ shiftUp(index) {if(index === 0) return const heap = this.heap const parentIndex = This.getparentindex (index) // getParentIndex(index) // When the value of the parent is greater than the current value, move up, If (heap[parentIndex] > this.heap[index]) {this.swap(parentIndex, ShiftUp (parentIndex) // Continue to move up}} /** * Delete the top of the heap * Due to the data structure of the heap, we cannot delete the top of the heap directly, we need to replace the bottom of the heap with the top of the heap. */ pop() {this.heap[0] = this.heap.pop() // Take the value from the top of the heap to the bottom of the heap: this.shiftdown (0) // push down} /** * push down * @param index */ shiftDown(index) {if(index >= this.length) return // Limit the value of const heap = this.heap const leftIndex = This.getleftindex (index) // Get the left child const rightIndex = this.getrightIndex (index) // Get the right child // When the current value is greater than the left child if(heap[index] > heap[leftIndex]) { this.swap(index, The value of the current node should be greater than the value of the right child node. The value should be taken when the left child node is swapped. The value of the left child is not necessarily smaller than the value of the right child // so even if the above method passes and swaps, Heap [index] > heap[rightIndex]) {this.swap(index, RightIndex) // swap this.shiftDown(rightIndex) // move down}} /** * Swap value * @param parentIndex subscript of the parent node * @param Index subscript of the child node */ swap(parentIndex, index) { const heap = this.heap const temp = heap[parentIndex] heap[parentIndex] = heap[index] heap[index] = temp } /** */ getParentIndex(index) {// >> The right shift operator is a binary number to the right, Return (index-1) >> 1 // return math.floor ((index-1) / 2)} /** * get the left child * @param index The current node subscript * / getLeftIndex (index) {/ / left shift operators Binary left an equivalent to take 2 | index * 2 + 1 return (index < < 1) + 1} / * * * * @ param access right child node The index of the current node subscript * / getRightIndex (index) {/ / left shift operators Binary left an equivalent to take 2 | index * 2 + 2 return (index < < 1) + 2} / * * * for roof * / Peek () {return this.heap[0]} /** * Gets the length of the heap */ size() {return this.heap. Length}} // gets the KTH maximum element // The idea is to set the heap top to the minimum value by using the minimum heap and then limit the current heap length to k. Var findKthLargest = function(largest, nums) k) { const h = new MinHeap() nums.forEach(v => { h.insert(v) if(h.size() > k) { h.pop() } }) return h.peek() }Copy the code

Four,

In fact, the main problem is sorting, sorting after this problem is solved.

This article is participating in the “Nuggets 2021 Spring Recruitment Campaign”, click to see the details of the campaign