.
2019-11-13 星期二 开始吧 库里的深夜食堂
给定一个 N*N 的矩阵 (这么正经的翻译你一定不喜欢，所以你直接理解成二维数组就行了)。它的每行和每列都按照升序排序，问题是，通过一个给定的数值 K，找出这个二维数组中第 K 小的数。 先说下我最初的想法，这个题目归别到 Binary Serach, 那就肯定是可以用二分的思想的，但是按照我之前刷的二分题目，就算获取到中位数，我也并不能确定这个中位数的位置大小排在数组的整体大小位置，我只能确定我这一行的位置，我也只知道我当前位置的上一行对应的列比我小而已。
之所以这样想，是我潜意思里都把二维结构 + 二分查找，对应的中位数默认理解为就是索引位置。跳出这个思维空间再思考，查找二维数组中第 K 小的数那必然存在于二维数组当中啊。调整思路。开始二分模板解题。之前写过一篇而二分的文章)
left 初始值即数组最小值 $left=$matrix [0][0]，right 初始值即数组最大值 $right=$matrix [行数 - 1][列数 - 1];
开始往中间挤压。先求得中位数。这个的中位数指的是具体的值，而不是索引位置的意思。只要统计这个二维数组中小于等于当前中位数的个数。如果统计的个数小于给定值 K, 说明第 K 小的值并不在 left 和 中位数之间，而是在中位数 + 1 至 right 之间，所以重新赋值 left (不包括中位数) , 否则的话赋值 right。最后随意返回 left 或者 right。
/**
* @param Integer[][] $matrix
* @param Integer $k
* @return Integer
*/
function kthSmallest($matrix, $k)
{
$row = count($matrix);
$col = count($matrix[0]);
$left = $matrix[0][0];
$right = $matrix[$row - 1][$col - 1];
while ($left < $right) {
$middle = ($left + $right) >> 1;
$count = $this->lessMiddleAmount($matrix, $middle, $row - 1, $col);
if ($count < $k) {
$left = $middle + 1;
} else {
$right = $middle;
}
}
return $left;
}
function lessMiddleAmount($matrix, $middle, $row, $col)
{
$left = 0;
$count = 0;
while ($row >= 0 && $left < $col) {
if ($matrix[$row][$left] <= $middle) {
$count += $row + 1;
$left++;
} else {
$row--;
}
}
return $count;
}
上面 left 为什么不包括中位数？可以从两个角度分析，按照逻辑思维的角度，既然统计小于等于中位数的个数都比 K 小，我还咋么去争取当上第 K 小的数？？？另一角度，从当前运行的程序上来分析，获取的中位数我习惯这样写 ($left+$right)>>1 , 如果 left + right 是奇数的情况下并没有争议，如果是偶数呢？那么我这里将得到一个左中位数。程序往下面走，如果走的是 if($count<$k) 这个分支的话，并且我的 $left 包含了中位数，会发生什么？答案很明显，程序进入死循环。直至你收到一个 Time Limit Exceeded 的错误。
