378. Kth Smallest Element in a Sorted Matrix

[Tcdian]

378. Kth Smallest Element in a Sorted Matrix

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

Example

matrix = [
   [ 1,  5,  9],
   [10, 11, 13],
   [12, 13, 15]
],
k = 8,

return 13.

Note

• 你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

[Tcdian]

Solution 1 ( Merge Sort )

• JavaScript Solution

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    const sorted = mergeSorted(0, matrix.length - 1);
    return sorted[k - 1];

    function mergeSorted(left, right) {
        if (left === right) {
            return matrix[left];
        }
        const mid = (left + right) >> 1;
        let leftSorted = mergeSorted(left, mid);
        let rightSorted = mergeSorted(mid + 1, right);
        let leftPatrol = 0;
        let rightPatrol = 0;
        const sorted = [];
        while(leftPatrol < leftSorted.length && rightPatrol < rightSorted.length) {
            if (leftSorted[leftPatrol] <= rightSorted[rightPatrol]) {
                sorted.push(leftSorted[leftPatrol++]);
            } else {
                sorted.push(rightSorted[rightPatrol++]);
            }
        }
        return [...sorted, ...leftSorted.slice(leftPatrol), ...rightSorted.slice(rightPatrol)];
    }
};

• TypeScript Solution

function kthSmallest(matrix: number[][], k: number): number {
    const sorted = mergeSorted(0, matrix.length - 1);
    return sorted[k - 1];

    function mergeSorted(left: number, right: number): number[] {
        if (left === right) {
            return matrix[left];
        }
        const mid = (left + right) >> 1;
        let leftSorted = mergeSorted(left, mid);
        let rightSorted = mergeSorted(mid + 1, right);
        let leftPatrol = 0;
        let rightPatrol = 0;
        const sorted = [];
        while(leftPatrol < leftSorted.length && rightPatrol < rightSorted.length) {
            if (leftSorted[leftPatrol] <= rightSorted[rightPatrol]) {
                sorted.push(leftSorted[leftPatrol++]);
            } else {
                sorted.push(rightSorted[rightPatrol++]);
            }
        }
        return [...sorted, ...leftSorted.slice(leftPatrol), ...rightSorted.slice(rightPatrol)];
    }
};

[Tcdian]

Solution 2  ( Binary Search )

• JavaScript Solution

/**
 * @param {number[][]} matrix
 * @param {number} k
 * @return {number}
 */
var kthSmallest = function(matrix, k) {
    let left = matrix[0][0];
    let right = matrix[matrix.length - 1][matrix[0].length - 1];
    while(left < right) {
        const mid = (left + right) >> 1;
        let count = findLte(matrix, mid);
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

function findLte(matrix, target) {
    let i = 0;
    let j = matrix[0].length - 1;
    let count = 0;
    while (i < matrix.length && j >= 0) {
        if (matrix[i][j] <= target) {
            count += j + 1;
            i++;
        } else {
            j--;
        }
    }
    return count;
}

• TypeScript Solution

function kthSmallest(matrix: number[][], k: number): number {
    let left = matrix[0][0];
    let right = matrix[matrix.length - 1][matrix[0].length - 1];
    while(left < right) {
        const mid = (left + right) >> 1;
        let count = findLte(matrix, mid);
        if (count < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
};

function findLte(matrix: number[][], target: number): number {
    let i = 0;
    let j = matrix[0].length - 1;
    let count = 0;
    while (i < matrix.length && j >= 0) {
        if (matrix[i][j] <= target) {
            count += j + 1;
            i++;
        } else {
            j--;
        }
    }
    return count;
}