day01 --- PHP实现 n*n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素

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

第一次双百：

二分查找思路：

1. 从矩阵的左下角开始遍历元素，矩阵中当不大于 mid 的数大于等于 k 时，说明目标值一定在左半边范围内

2. 否则在右半边范围内

3. 从矩阵左上角最小值，右下角最大值，确定 mid 值

代码如下：

function kthSmallest($matrix, $k) {$n = count($matrix);$min = $matrix[0][0];$max = $matrix[$n-1][$n-1];while ($min <= $max) {$mid = $max - floor(($max - $min) / 2);if (isIn($matrix, $mid, $k, $n)) {$max = $mid - 1;} else {$min = $mid + 1;}}return $min;
}function isIn($arr, $mid, $k, $n)
{$x = $n - 1; // 行$y = 0;$num = 0;while ($y < $n && $x >= 0) {if ($arr[$x][$y] <= $mid) {$num += $x + 1;$y++;} else {$x--;}}return $num >= $k;
}

如果还有疑问的话，可以参考：leetcode上面的题解。