论坛 › 其它 › JavaScript大根堆建队On复杂度

李恒道 发表于 2024-9-11 08:25:06

JavaScript大根堆建队On复杂度

只实现了一些基础的函数
```js
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;
      this.heap = this.heap;
      this.border--;
      this.downNode(0)
      return temp
    }
    swap(x, y) {
      let temp = this.heap
      this.heap = this.heap
      this.heap = 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 < this.heap ? right : left
            } else {
                maxIndex = left <= this.border ? right : left
            }
            if (this.heap < this.heap) {
                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 发表于 2024-9-11 09:20:44

道长还重视算法练习hh

李恒道 发表于 2024-9-11 09:29:19

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

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

wuxin0011 发表于 2024-9-13 09:22:41

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

李恒道 发表于 2024-12-24 06:19:31

wuxin0011 发表于 2024-9-13 09:22
刷题进1w名差不多需要350道

现在也太卷了...
我操
300题了没排名

查看完整版本: JavaScript大根堆建队On复杂度