分享一道有趣的 Leetcode 题目

开篇

今天日常刷题的时候，依旧选择 tag 是 Binary Serach 类型的题目。这还是道热门的题目，看点赞数就知道了。

题目介绍

给定一个 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 的错误。

运行结果也是妥妥的 AC。(千万别相信这个运行效率，都是骗人的😃)

本作品采用《CC 协议》，转载必须注明作者和本文链接