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

给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。
请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

示例：

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

返回 13
提示：
你可以假设 k 的值永远是有效的，1 ≤ k ≤ n2 。

刚开始一读了这个题第一思路就是先二维转一位，然后排序，然后再根据k和键的关系直接取，本来以为没这么简单，就先尝试了一下桶排的思想，找到matrix 数组最右下角的那个值是最大的，然后开一个最大值+1的数组，初始值都设为0，遍历matrix 数组，值作为键存起来，出现了一次就对该键加1，感觉这个方法思想没啥问题，提交的时候就是内存超限了，然后就还是用的第一种方法去尝试提交，然后就过了，，没啥心理准备，这里贴一下过的代码(很简单)：

class Solution {

    /**
     * @param Integer[][] $matrix
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($matrix, $k) {
        $res = [];
        foreach ($matrix as $value) {
        	foreach ($value as $val) {
        		$res[] = $val;
        	}
        }
        sort($res);
       	return $res[$k-1];
    }
}

后面看了官方的解题方法，除了上面过了的直接转一位数组排序的方法，还有归并排序，二分查找的方法，二分查找的方法是完全利用了有序矩阵列与行的关系，时间复杂度最低。这里矩阵是二维的二分查找，先找一个中间值，把矩阵的所有值通过这个中间值分成两部分，左上角的值是比中间值小的，右下角的值比中间值大的。分别得到前一部分的个数，和传入的k做比较，如果比k值大，说明值在左上角部分，如果比k值小，那就是在右下角部分。然后再分，继续查找，直到找到值。在最后这一步一直分着查找的时候遇到了很多问题，一直没有方法准确的找到值，没有通过，，这里贴出一下代码：

class Solution {

    /**
     * @param Integer[][] $matrix
     * @param Integer $k
     * @return Integer
     */
    function kthSmallest($matrix, $k) {
    	$count = count($matrix);
        $low = $matrix[0][0];
        $high = $matrix[$count-1][$count-1];
        $prev = 0;
        while (1) {
        	$mid = intval(($low+$high)/2);
	        $arr =  $this->getNum($matrix, $mid);
	        if ($arr['res'] == $prev) {
	        	return $mid;
	        }
	        $prev = $arr['res'];
	        if ($k < $arr['res']) {
	        	$high = $mid;
	        } elseif ($k > $arr['res']) {
	        	$low = $mid;
	        } else {
	        	if ($arr['flag']) {
					return $mid;
	        	} else {
	        		$high = $mid;
	        	}
	        }
        }  
    }
    /**
    * @param array $matrix
    * @param int $mid
    * @return int $res
     */
    function getNum($matrix, $mid)
    {
    	$count = count($matrix);
    	
    	//记录行数
    	$row = $count-1;
    	$col = 0;
    	//用于记录总数
    	$res = 0;
    	$flag = 0;
    	//当行数小于0也就是不在数组中了结束查找
    	while ($row >= 0 && $col <= $count-1) {
    		//开始值从最左下角开始找
    		$start = $matrix[$row][$col];
    		//比mid小的话往右走，列加一
    		if ($start < $mid) {
    			$res += $row+1;
    			$col++;
    		} elseif ($start == $mid) {
    			$res += $row+1;
    			$col++;
    			$flag = 1;
    		}else {
    			$row--;
    		}
    	}
    	return ['res' => $res, 'flag' => $flag];
    }
}