JavaScript大根堆建队On复杂度

李恒道

只实现了一些基础的函数

class MaxHeadp {
    heap
    border
    constructor(nums) {
        this.heap = nums;
        this.border = nums.length - 1
        this.initHeap();
    }
    initHeap() {
        const endIndex = this.getTopNode(this.border)
        for (let index = endIndex; index >= 0; index--) {
            this.downNode(index)
        }
    }
    haveNum() {
        return this.border + 1
    }
    pop() {
        if (this.border === -1) {
            return undefined
        }
        const temp = this.heap[0];
        this.heap[0] = this.heap[this.border];
        this.border--;
        this.downNode(0)
        return temp
    }
    swap(x, y) {
        let temp = this.heap[x]
        this.heap[x] = this.heap[y]
        this.heap[y] = temp
    }
    downNode(index) {
        let left = this.getLeftNode(index);
        let right = this.getRightNode(index);
        while (left <= this.border || right <= this.border) {
            let maxIndex = undefined
            if (left <= this.border || right <= this.border) {
                maxIndex = this.heap[left] < this.heap[right] ? right : left
            } else {
                maxIndex = left <= this.border ? right : left
            }
            if (this.heap[index] < this.heap[maxIndex]) {
                this.swap(index, maxIndex)
                index = maxIndex
                left = this.getLeftNode(index);
                right = this.getRightNode(index);
            } else {
                break;
            }
        }
    }
    getTopNode(index) {
        return Math.floor((index - 1) / 2)
    }
    getLeftNode(index) {
        return (index + 1) * 2 - 1
    }
    getRightNode(index) {
        return (index + 1) * 2
    }
}

var findKthLargest = function (nums, k) {
    const heap = new MaxHeadp(nums)
    let times = 0
    let lastNum = undefined
    while (heap.haveNum() != 0) {
        const num = heap.pop()
        if (num !== lastNum) {
            times++
        }
        if (times == k) {
            return num
        }
    }
    return -1
};

wuxin0011

道长还重视算法练习hh

李恒道

wuxin0011 发表于 2024-9-11 09:20
道长还重视算法练习hh

主要想挑战一下leetcode能不能进一万名
但是目前遥遥无期
刚打100道
差不多进度也就15%吧

wuxin0011

刷题进1w名差不多需要350道