“This is the 19th day of my participation in the First Challenge 2022. For details: First Challenge 2022”

The KTH largest element in the leetcode-215 array

Subject to introduce

Given an integer array nums and an integer k, return the KTH largest element in the 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 =2Output:5
Copy the code

Example 2

Input:3.2.3.1.2.4.5.5.6] and k =4Output:4
Copy the code

Tip:

  • 1 <= k <= nums.length <= 10^4
  • -10^4 <= nums[i] <= 10^4

Their thinking

Idea 1: Sort directly

Sort (nums); sort (nums); sort (nums); sort (numS)

The problem solving steps

  1. rightnumsSort the array in ascending order
  2. Returns the subscript of the sorted arraynums.length - kThe value of the

The problem solving code

var findKthLargest = function(nums, k) {
    nums.sort((a, b) = > a - b)
    return nums[nums.length - k]
};
Copy the code

Idea 2: Small top stack

If the size of the small top heap is less than K, insert the element directly into the small top heap and adjust the structure of the small top heap upward. If the size of the small top heap is equal to K, Only values larger than the top element in the small top heap can replace the top element in the small top heap, then adjust down to maintain the structure of the small top heap, and finally return the top element as the KTH largest element in the array when iterating through the entire NUMS array

The problem solving steps

  1. Create a small top heapminHeap, the size ofk
  2. Traverse the entirenumsIntegers in an array, insert all integers into the small top heap
  3. Returns the small top heapminHeapThe heap top element of

The problem solving code

var findKthLargest = function(nums, k) {
    // Create a small top heap of size k
    const minHeap = new Heap(k)
    // Insert all integers into the small top heap
    while(nums.length) {
        minHeap.push(nums.pop())
    }
    // Returns the top element of the small top heap
    return minHeap.pop()
};

class Heap {
    constructor(k) {
        this.arr = []
        this.k = k
    }

    Return the current size of the small top heap
    size() {
        return this.arr.length
    }

    // Insert elements into the small top heap
    push(val) {
        if (this.size() < this.k) {
            this.arr.push(val)
            this._sortBack()
        } else if (val > this.arr[0]) {
            this.arr[0] = val
            this._sortFront()
        }
    }

    // Pop up the top element of the small top heap
    pop() {
        const val = this.arr[0]
        const back = this.arr.pop()
        if (this.arr.length) {
            this.arr[0] = back
            this._sortFront()
        }
        return val
    }

    // Adjust the structure of the small top heap upwards
    _sortBack() {
        let i = this.arr.length - 1
        while(i > 0 && this.arr[i] < this.arr[Math.floor((i - 1) / 2)]) {[this.arr[i], this.arr[Math.floor((i - 1) / 2)]] = [this.arr[Math.floor((i - 1) / 2)].this.arr[i]]
            i = Math.floor((i - 1) / 2)}}// Adjust the structure of the small top heap downward from the top
    _sortFront() {
        let i = 0 
        while (i * 2 + 1 < this.size()) {
            let temp = i
            if (this.arr[temp] > this.arr[i * 2 + 1]) temp = i * 2 + 1
            if (i * 2 + 2 < this.size() && this.arr[temp] > this.arr[i * 2 + 2]) temp = i * 2 + 2
            if (temp === i) break
            [this.arr[i], this.arr[temp]] = [this.arr[temp], this.arr[i]]
            i = temp 
        }
    }
}
Copy the code