378.有序矩阵中第K小的元素

链接：378.有序矩阵中第K小的元素
难度：Medium
标签：数组、二分查找、矩阵、排序、堆（优先队列）
简介：给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。

题解 1 - typescript

• 编辑时间：2020-07-02
• 执行用时：100ms
• 内存消耗：52.8MB
• 编程语言：typescript
• 解法介绍：构建小顶堆进行读取。

class Heap {
  get size(): number {
    return this._elemenets.length;
  }
  constructor(private _elemenets: number[]) {
    this.heapify();
  }
  heapify(): void {
    for (let i = (this.size >> 1) - 1; i >= 0; i--) {
      this.siftDown(i);
    }
  }
  remove(): number {
    const root = this._elemenets[0];
    this._elemenets[0] = this._elemenets.pop() as number;
    this.siftDown(0);
    return root;
  }
  siftDown(index: number) {
    const element = this._elemenets[index];
    const half = this.size >> 1;
    while (index < half) {
      let childIndex = (index << 1) + 1;
      let child = this._elemenets[childIndex];
      const rightIndex = childIndex + 1;
      if (rightIndex < this.size && this._elemenets[rightIndex] < child) {
        child = this._elemenets[(childIndex = rightIndex)];
      }
      if (element <= child) break;
      this._elemenets[index] = child;
      index = childIndex;
    }
    this._elemenets[index] = element;
  }
}
function kthSmallest(matrix: number[][], k: number): number {
  const heap = new Heap(matrix.reduce((total, value) => total.concat(value), []));
  while (--k !== 0) {
    heap.remove();
  }
  return heap.remove();
}

题解 2 - c

• 编辑时间：2021-11-30
• 执行用时：32ms
• 内存消耗：8.1MB
• 编程语言：c
• 解法介绍：二分查找，根据矩阵有序特性。

int check(int **matrix, int n, int num) {
    int row = n - 1, col = 0, cnt = 0;
    while (row >= 0) {
        while(col < n && matrix[row][col] <= num) col++;
        cnt += col;
        row--;
    }
    return cnt;
}
int kthSmallest(int** matrix, int matrixSize, int* matrixColSize, int k){
    int l = matrix[0][0], r = matrix[matrixSize - 1][matrixSize - 1], m;
    while (l < r) {
        m = (l + r) >> 1;
        int cnt = check(matrix, matrixSize, m);
        if (cnt >= k) r = m;
        else l = m + 1;
    }
    return l;
}

题解 3 - typescript

• 编辑时间：2020-07-02
• 执行用时：112ms
• 内存消耗：51.4MB
• 编程语言：typescript
• 解法介绍：拍平后排序输出。

function kthSmallest(matrix: number[][], k: number): number {
  return matrix.reduce((total, value) => total.concat(value), []).sort((a, b) => a - b)[k - 1];
}