This is the 8th day of my participation in Gwen Challenge.

Problem 215. The KTH largest element in an array

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: 5 example 2:

Input: [3,2,3,1,2,4,5,5,6] and k = 4 output: 4

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

Source: LeetCode link: leetcode-cn.com/problems/kt… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.

Method one: fast row

Sort the entire array using a better sorting method to find the KTH largest element.

Reference code

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
var findKthLargest = function(nums, k) {
    const sortedArr = nums.sort((a,b) = >a-b)
    return sortedArr[nums.length-k]
};
Copy the code

Method two: fast platoon optimization

Divide and conquer in quicksort, each time you get a benchmark, you can determine the final position of the benchmark, that is, the final order in the ordered array. Compare the position of the benchmark and the K element we want to find, constantly narrow the search scope, know that the final benchmark is to find the position, you can realize the sorting of some elements to find the K element.

-_ – | | don’t know why on LeetCode timeouts, and the same case I local no problem…

code

/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
var findKthLargest = function(nums, k) {
    const len = nums.length
    const target = len - k
    let left = 0
    let right = len-1
    while (true) {
        // Divide and conquer, each time determine the location of a pivort in the array. Compare the location with the target location to determine whether to continue the search
        const resultIndex = partition(nums,left,right)
        if(resultIndex < target){
            left = resultIndex+1
        }else if(resultIndex > target){
            right = resultIndex - 1
        }else{
            return nums[resultIndex]
        }
    }
};
function partition(nums,left,right) {
    const len = right - left + 1
    const pivort = Math.floor(Math.random() * len )+left
    const lessThanPivortValue = nums.slice(left,right+1).filter((item,index) = >{
        constflag = (item <= nums[pivort]) && ((index+left) ! == pivort)return flag
    })
    const bigThanPivortValue = nums.slice(left,right+1).filter((item,index) = >{
        constflag = item > nums[pivort]&& (index+left) ! == pivortreturn flag
    })
    constnewArr = lessThanPivortValue.concat([nums[pivort]],bigThanPivortValue) nums.splice(left,len,... newArr)return lessThanPivortValue.length
}
Copy the code

Method three: heap implementation

Use the heap to store K elements and return the KTH element after iterating through the array. So you can use the smallest heap, where the top of the heap is the KTH largest element.

The smallest heap is stored as a complete binary tree, so that there is a particular one that counts from root 1, whose left subtree is 2i times that of the nearest parent node I, and whose right subtree is 2I +1 times that of the nearest parent node I. So we start at 1 and store the valid data in the heap.

The property of the smallest heap is that the smallest is on top and the largest is on the bottom.

When we insert an element into the heap, we put it at the end. If the element is smaller than its parent, it should swap places with the parent, and so on, to find its final size.

Similarly, when we remove the top of the heap, we put the last element on top of the heap, which minimizes the structure of the heap. The top of the heap should be smaller than its children, so you keep comparing and finding the right place for the top element.

Reference code

class MinHeap{
    constructor(){
        // The 0th element is not stored, but is stored from 1
        this.heap = [0]}insert(data){
        // Insert new data and sort the data so that the smallest element is on top of the heap
        this.heap.push(data)
        this.shiftUp(this.heap.length-1)}shiftUp(index){
        // Float the element up, compare the size with the parent element,
        const parentIndex = this.getParentIndex(index)
        if(index === 0 || parentIndex === 0) return
        if (this.heap[parentIndex] > this.heap[index]) {
            this.swap(parentIndex,index)
            this.shiftUp(parentIndex)
        }
    }

    getParentIndex(i){
        return parseInt(i/2)}getLeftIndex(i){
        return 2 * i
    }

    getRightIndex(i){
        return 2 * i +1
    }

    swap(i1, i2){
        const temp = this.heap[i1]
        this.heap[i1]= this.heap[i2]
        this.heap[i2] = temp
    }

    delete(){
        this.heap[1] = this.heap.pop()
        this.shiftDown(1)}shiftDown(index){
        // The element sinks to compare the size of the child element
        const leftIndex = this.getLeftIndex(index)
        const rightIndex = this.getRightIndex(index)
        if (this.heap[leftIndex] <this.heap[index]) {
            this.swap(leftIndex,index)
            this.shiftDown(leftIndex)
        }
        if (this.heap[rightIndex] <this.heap[index]) {
            this.swap(rightIndex,index)
            this.shiftDown(rightIndex)
        }
    }

    getSize(){
        return this.heap.length - 1
    }

    getPeek(){
        return this.heap[1]}}/ * * *@param {number[]} nums
 * @param {number} k
 * @return {number}* /
var findKthLargest = function(nums, k) {
    const heap = new MinHeap()
    for (let index = 0; index < nums.length; index++) {
        heap.insert(nums[index])
        const size = heap.getSize()
        if(size > k){
            heap.delete()
        }
    }
    return heap.getPeek()
};
Copy the code