【LeetCode】378. 有序矩阵中第 K 小的元素（js 实现）

1、题目：

2、实现

（1）方法一：

直接将矩阵转换为一维数组，再将一维数组进行排序，最后取第k个元素即可。

代码：

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    // 将矩阵转换为数组，再对数组进行排序
    let arr = [];
    for(let i=0; i<matrix.length; i++) {
        for(let j=0; j<matrix[0].length; j++) {
            arr.push(matrix[i][j]);
        }
    }
    arr.sort((a,b)=>{return a-b;});
    return arr[k-1];
};

（2）方法二：

代码：（注意：要对mid下取整，否则报错）

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    // 经过观察，左上角元素为min，右下角元素为max，获取它们的坐标
    let m = matrix.length, n = matrix[0].length;
    let low = matrix[0][0], high = matrix[m-1][n-1];
    // 由于矩阵中有重复元素，所以包含等号
    while(low <= high) {
        let mid = Math.floor(low + (high - low) / 2);
        let count = 0;
        for(let i=0; i<m; i++) {
            for(let j=0; j<n && matrix[i][j]<=mid; j++) {
                // 获取比mid小的元素的个数
                count++;
            }
        }
        if(count < k) {
            // 结果在右边
            low = mid + 1;
        } else {
            // 结果在左边
            high = mid - 1;
        }
    }
    return low;
};

3、参考：