当前位置： 面试刷题>> 有序矩阵中的第k小元素 (经典算法题500道)
### 题目描述补充
给定一个 `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 示例代码
```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 示例代码
```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 示例代码
```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
```
**码小课网站中有更多相关内容分享给大家学习**，涵盖各种算法和数据结构等编程知识。