找到前 K 个最大的元素

[lgwebdream]

No description provided.

[lgwebdream]

扫描下方二维码，获取答案以及详细解析，同时可解锁800+道前端面试题。

[AAA611]

大顶堆

    class Heap {
      constructor(compare, values) {
        this.data = [...values]
        this._compare = compare
      }

      /**
       * @private
       * @param {number} i 
       * @param {number} j 
       */
      _swap(i, j) {
        let temp = this.data[i]
        this.data[i] = this.data[j]
        this.data[j] = temp
      }

      _shouldSwap(parentIndex, childIndex) {
        if (parentIndex < 0 || parentIndex >= this.size()) return false
        if (childIndex < 0 || childIndex >= this.size()) return false

        return this._compare(this.data[parentIndex], this.data[childIndex]) > 0
      }

      /**
       * 向上调整
       * @private
       * @param {number} startIndex
       */
      _heapifyUp(startIndex) {
        let childIndex = startIndex
        const parentIndex = Math.floor((childIndex - 1) / 2)

        if (this._shouldSwap(parentIndex, childIndex)) {
          this._swap(parentIndex, childIndex)
          childIndex = parentIndex
          this._heapifyUp(childIndex)
        }
      }

      /**
       * 向下调整
       * @private
       * @param {number} startIndex
       */
      _heapifyDown(startIndex) {
        let parentIndex = startIndex
        const leftIndex = 2 * parentIndex + 1
        const rightIndex = 2 * parentIndex + 2

        let childIndex = this._compare(this.data[leftIndex], this.data[rightIndex]) > 0 ? rightIndex : leftIndex

        if (this._shouldSwap(parentIndex, childIndex)) {
          this._swap(parentIndex, childIndex)
          parentIndex = childIndex
          this._heapifyDown(parentIndex)
        }
      }

      /**
       * @private
       * @param {number} index 
       */
      _heapifyDownUntil(index) {
        let parentIndex = 0;
        let leftIndex = 1;
        let rightIndex = 2;
        let childIndex;

        while (leftIndex < index) {
          childIndex = (this._compare(this.data[leftIndex], this.data[rightIndex]) > 0 && rightIndex < index) ? rightIndex : leftIndex

          if (this._shouldSwap(parentIndex, childIndex)) {
            this._swap(parentIndex, childIndex);
          }

          parentIndex = childIndex;
          leftIndex = (parentIndex * 2) + 1;
          rightIndex = (parentIndex * 2) + 2;
        }
      }

      /**
       * insert
       * @public
       * @param {*} val 
       * @returns {*} Heap
       */
      insert(val) {
        this.data.push(val)
        this._heapifyUp(this.size() - 1)

        return this
      }

      /**
       * pop
       * @public
       * @returns {*} root
       */
      pop() {
        const root = this.data[0]
        this.data[0] = this.data[this.size() - 1]
        this.data.pop()
        this._heapifyDown(0)

        return root
      }

      sort() {
        for (let i = this.size() - 1; i > 0; i -= 1) {
          this._swap(0, i);
          this._heapifyDownUntil(i);
        }
        return this.data;
      }

      /**
       * get the heap size
       * @public
       * @returns {number} heap size
       */
      size() {
        return this.data.length
      }

      /**
       * @public
       * @returns {boolean} isEmpty
       */
      isEmpty() {
        return this.size() === 0
      }

      /**
       * build Heap
       */
      buildHeap() {
        for (let i = 0; i < this.size(); i++) {
          this._heapifyUp(i)
        }

        return this
      }

      static heapify(compare, values) {
        return new Heap(compare, values).buildHeap()
      }
    }

    let nums = [5, 7, 1, 8, 9]
    function fn(nums, k) {
      const heap = Heap.heapify((a, b) => b - a, nums)
      for (let i = 1; i < k; i++) {
        heap.pop()
      }
      return heap.pop()
    }
    console.log(fn(nums, 2));

排序

    function fn1(nums, k) {
      if (nums.length === 1) {
        return nums[k - 1];
      }
      nums.sort((a, b) => b - a);
      return nums[k - 1];
    };