2022.2.22-第13题-215. 数组中的第K个最大元素

[yanggengzhen123]

https://leetcode-cn.com/problems/kth-largest-element-in-an-array/ 给定整数数组 nums 和整数 k，请返回数组中第 k 个最大的元素。 请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1: 输入: [3,2,1,5,6,4] 和 k = 2 输出: 5

示例 2: 输入: [3,2,3,1,2,4,5,5,6] 和 k = 4 输出: 4

[BambooSword]

// 利用堆排序解决本题
function findKthLargest(nums: number[], k: number): number {
    const heap = new Heap([], (a, b) => b - a > 0);
    const len = nums.length;
    for (let i = 0; i < len; i++) {
        if (heap.size() < k) {
            heap.offer(nums[i])
        } else {
            const min = heap.peek();
            if (min < nums[i]) {
                heap.poll()
                heap.offer(nums[i])

            }
        }
    }
    return heap.peek()

};

class Heap {
    data: number[]
    comparer: (a: number, b: number) => boolean
    constructor(data: number[] = [], comparer: (a: number, b: number) => boolean = (a, b) => a - b > 0) {
        this.data = data
        this.comparer = comparer;
        this.heapify()

    }
    heapify() {
        const len = this.size()
        for (let i = 1; i < len; i++) {
            this.bubbleUp(i);
        }

    }
    bubbleUp(index: number) {
        while (index > 0) {
            const parent = (index - 1) >> 1;
            if (this.comparer(this.data[index], this.data[parent])) {
                this.swap(parent, index);
                index = parent
            } else {
                break;
            }
        }

    }
    peek() {
        return this.data[0];
    }
    offer(val: number) {
        const size = this.size()
        this.data.push(val);
        this.bubbleUp(size)
    }
    poll() {
        if (this.size() === 0) return null;
        if (this.size() === 1) return this.data.pop()
        const res = this.data[0];

        this.data[0] = this.data.pop();
        this.bubbleDown(0);
        return res;

    }

    bubbleDown(index) {
        const len = this.size();
        while (index < len) {
            const left = index * 2 + 1;
            const right = index * 2 + 2;
            let findIndex = index;
            if (left < len && this.comparer(this.data[left], this.data[findIndex])) {
                findIndex = left
            }
            if (right < len && this.comparer(this.data[right], this.data[findIndex])) {
                findIndex = right
            }
            if (findIndex !== index) {
                this.swap(findIndex, index);
                index = findIndex
            } else {
                break;
            }
        }

    }
    size() {
        return this.data.length
    }
    swap(ind1: number, ind2: number) {
        [this.data[ind1], this.data[ind2]] = [this.data[ind2], this.data[ind1]];
    }

}

[icodeish]

function findKthLargest(nums, k) {
    const len = nums.length
    const targetIndex = len - k
    let left = 0,
        right = len - 1
    while (left < right) {
        const index = partition(nums, left, right)
        if (index === targetIndex) {
            return nums[index]
        } else if (index < targetIndex) {
            left = index + 1
        } else {
            right = index - 1
        }
    }
    return nums[left]
}
function partition(nums, start, end) {
    const povit = nums[start]
    while (start < end) {
        while (start < end && nums[end] >= povit) {
            end--
        }
        nums[start] = nums[end]
        while (start < end && nums[start] < povit) {
            start++
        }
        nums[end] = nums[start]
    }
    nums[start] = povit
    return start
}

[yanggengzhen123]

//快速排序
function findKthLargest(nums: number[], k: number): number {
    const quickSort = (list: number[]) => {
        if(list.length === 0 || list.length === 1){
            return list
        }
        // 中位index
        let index = Math.floor(list.length/2)
        let currentItem = list.splice(index,1)
        let leftList:number[] = []
        let rightList:number[] = []
        list.forEach(item => {
            if(item >= currentItem){
                leftList.push(item)
            }else{
                rightList.push(item)
            }
        })
        return quickSort(leftList).concat(currentItem).concat(quickSort(rightList))
    }
    const res =  quickSort(nums)
    return res[k - 1]
};