题目描述补充

给定一个 m x n 的矩阵（二维数组），其中的元素已按非递减顺序排列（即，对于所有 i < j 有 matrix[i][0] <= matrix[j][0]，且对于所有 i, j 使得 matrix[i][j] <= matrix[i][j+1]）。请编写一个函数来找到并返回矩阵中的第 k 小元素。

注意：你可以假设 k 的值总是有效的，即 1 <= k <= m * n。

示例

输入：

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

输出：

13

PHP 示例代码

function findKthNumber($matrix, $k) {
    $m = count($matrix);
    $n = count($matrix[0]);
    $left = $matrix[0][0];
    $right = $matrix[$m-1][$n-1];

    while ($left < $right) {
        $mid = $left + floor(($right - $left) / 2);
        $count = countSmallerOrEqual($matrix, $mid);
        
        if ($count < $k) {
            $left = $mid + 1;
        } else {
            $right = $mid;
        }
    }

    return $left;
}

function countSmallerOrEqual($matrix, $target) {
    $count = 0;
    $m = count($matrix);
    $n = count($matrix[0]);
    $row = $m - 1;
    $col = 0;

    while ($row >= 0 && $col < $n) {
        if ($matrix[$row][$col] <= $target) {
            $count += $row + 1;
            $col++;
        } else {
            $row--;
        }
    }

    return $count;
}

// 使用示例
$matrix = [
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15]
];
$k = 8;
echo findKthNumber($matrix, $k); // 输出 13

Python 示例代码

def findKthNumber(matrix, k):
    def count_smaller_or_equal(target):
        count = 0
        row, col = len(matrix) - 1, 0
        while row >= 0 and col < len(matrix[0]):
            if matrix[row][col] <= target:
                count += row + 1
                col += 1
            else:
                row -= 1
        return count

    left, right = matrix[0][0], matrix[-1][-1]
    while left < right:
        mid = left + (right - left) // 2
        if count_smaller_or_equal(mid) < k:
            left = mid + 1
        else:
            right = mid
    return left

# 使用示例
matrix = [
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15]
]
k = 8
print(findKthNumber(matrix, k))  # 输出 13

JavaScript 示例代码

function findKthNumber(matrix, k) {
    function countSmallerOrEqual(target) {
        let count = 0;
        let row = matrix.length - 1;
        let col = 0;
        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] <= target) {
                count += row + 1;
                col++;
            } else {
                row--;
            }
        }
        return count;
    }

    let left = matrix[0][0];
    let right = matrix[matrix.length - 1][matrix[0].length - 1];
    while (left < right) {
        let mid = Math.floor((left + right) / 2);
        if (countSmallerOrEqual(mid) < k) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }
    return left;
}

// 使用示例
const matrix = [
    [1, 5, 9],
    [10, 11, 13],
    [12, 13, 15]
];
const k = 8;
console.log(findKthNumber(matrix, k)); // 输出 13

码小课网站中有更多相关内容分享给大家学习，涵盖各种算法和数据结构等编程知识。