二维数组中的查找
题目描述
在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
提示：
0 <= n <= 1000
0 <= m <= 1000
题目分析
这题如果要用暴力法强行寻找的话，时间复杂度将会达到P(N*M)，而且没有有效的利用到题目给的每行每列都是递增的性质，显然不是标准答案，下面介绍一种思维比较灵活的充分利用题目条件的方法：
这是作为例子的矩阵，先取初始化点为18，至于为什么这么取后面再说，先看看算法的步骤：
-
当前处于18，18 > 9，所以18这一行都比9大，可以舍去这一行，往上走，形成新的矩阵
1 -
当前处于10，10 > 9，所以10这一行都比9大，可以舍去这一行，往上走，形成新的矩阵
2 -
当前处于3，3 < 9，所以3这一行都比9小，可以舍去这一行，往右走，形成新的矩阵
3 -
当前处于6，6 < 9，所以6这一行都比9小，可以舍去这一行，往右走，形成新的矩阵
4 -
当前位于9，返回True
5
步骤走完了，现在解释一下为什么要选择左下角的点作为起始点（其实相信大家都明白的差不多了），因为它是最后一行最小的元素，同时也是第一行最大的元素，Target比它大的时候就能排除一列，Target比它小的时候就能排除一行，所以无论情况怎么样，都能使下一次寻找的矩阵范围变小，而左上角和右下角的数是做不到的，所以我们可以从左下和右上出发。
时间复杂度：显然O(M+N)
空间复杂度：O(1)
fun findNumberIn2DArray(matrix: Array<IntArray>, target: Int): Boolean {
var x = matrix.size - 1
var y = 0
while (x >= 0 && y < matrix[0].size) {
if (matrix[x][y] == target)
return true
if (matrix[x][y] > target)
x--
else
y++
}
return false
}
