极客时间返利平台,你可以在上边通过山月的链接购买课程,并添加我的微信 (shanyue94) 领取返现。

# 如何求数组中的 TOP k

更多描述

求数组中的前 N 个最大的数

Issue

欢迎在 Gtihub Issue 中回答此问题: Issue 290 (opens new window)

  1. 取数组中前 k 个数做小顶堆,堆化
  2. 数组中的其它数逐一与堆顶元素比较,若大于堆顶元素,则插入该数

时间复杂度 O(nlg(k))

Author

回答者: manyyuri (opens new window)

实现一个优先队列类,默认大顶堆,传入(x,y)=>x>y 比较函数则为小顶堆。 首先将前 k 个数 insert,之后的数字如果大于栈顶元素(栈顶元素为堆中最小值),delTop 删除栈顶元素,然后 insert 该数。 维护一个 size 为 k 的小顶堆。 最后堆中元素即为数组中最大的 k 个元素。

class PriorityQueue {
  constructor(
    // 默认大顶堆
    cmp = (x, y) => {
      return x < y;
    }
  ) {
    this.queue = [];
    this.N = 0;
    this.cmp = (i, j) => {
      return cmp(this.queue[i], this.queue[j]);
    };
    this.parent = function (x) {
      return Math.floor(x / 2);
    };
    this.left = function (x) {
      return x * 2;
    };
    this.right = function (x) {
      return x * 2 + 1;
    };
    this.exch = (x, y) => {
      let temp = this.queue[x];
      this.queue[x] = this.queue[y];
      this.queue[y] = temp;
    };
  }
  swim(k) {
    const { cmp, parent, exch } = this;
    while (k > 1 && cmp(parent(k), k)) {
      exch(parent(k), k);
      k = parent(k);
    }
  }
  sink(k) {
    const { left, right, exch, N, cmp } = this;
    while (left(k) <= N) {
      let older = left(k);
      if (right(k) <= N && cmp(older, right(k))) {
        older = right(k);
      }
      if (cmp(older, k)) break;
      exch(older, k);
      k = older;
    }
  }
  top() {
    return this.queue[1];
  }
  delTop() {
    const { queue, exch } = this;
    let top = queue[1];
    exch(1, this.N);
    queue.pop();
    this.N--;
    this.sink(1);
    return top;
  }
  insert(x) {
    this.N++;
    this.queue[this.N] = x;
    this.swim(this.N);
  }
  size() {
    return this.N;
  }
}

function TopK(arr, k) {
  // 传入cmp,设置为小顶堆
  let pq = new PriorityQueue((x, y) => x > y);
  let i = 0;
  for (i = 0; i < k; i++) {
    pq.insert(arr[i]);
  }
  for (; i < arr.length; i++) {
    if (arr[i] > pq.top()) {
      pq.delTop();
      pq.insert(arr[i]);
    }
  }
  console.log("TOP K应为:", arr.sort((a, b) => b - a).splice(0, k));

  console.log("求出的TOP k:");
  // 排序,整理,方便对照
  pq.queue.sort((a, b) => b - a).pop();
  console.log(pq.queue);
}
let arr = [10, 15, 2, 6, 4, 5, 7, 3, 6, 14, 3, 12, 14, 13, 16, 1, 8];
TopK(arr, 10);
Last Updated: 11/27/2021, 6:11:48 PM