二維數(shù)組中的查找
題目描述
在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序械念，每一列都按照從上到下遞增的順序排序崇堰。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)菱涤，判斷數(shù)組中是否含有該整數(shù)。
示例：
[
[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
題目分析
這題如果要用暴力法強(qiáng)行尋找的話攻走，時(shí)間復(fù)雜度將會(huì)達(dá)到P(N*M)，而且沒(méi)有有效的利用到題目給的每行每列都是遞增的性質(zhì)此再，顯然不是標(biāo)準(zhǔn)答案昔搂，下面介紹一種思維比較靈活的充分利用題目條件的方法：
這是作為例子的矩陣，先取初始化點(diǎn)為18输拇，至于為什么這么取后面再說(shuō)摘符，先看看算法的步驟：
-
當(dāng)前處于18，18 > 9淳附，所以18這一行都比9大议慰，可以舍去這一行，往上走奴曙，形成新的矩陣
1 -
當(dāng)前處于10别凹，10 > 9，所以10這一行都比9大洽糟，可以舍去這一行炉菲，往上走，形成新的矩陣
2 -
當(dāng)前處于3坤溃，3 < 9拍霜，所以3這一行都比9小，可以舍去這一行薪介，往右走祠饺，形成新的矩陣
3 -
當(dāng)前處于6，6 < 9汁政，所以6這一行都比9小道偷，可以舍去這一行缀旁，往右走，形成新的矩陣
4 -
當(dāng)前位于9勺鸦，返回True
5
步驟走完了并巍，現(xiàn)在解釋一下為什么要選擇左下角的點(diǎn)作為起始點(diǎn)（其實(shí)相信大家都明白的差不多了），因?yàn)樗亲詈笠恍凶钚〉脑鼗煌荆瑫r(shí)也是第一行最大的元素懊渡，Target比它大的時(shí)候就能排除一列，Target比它小的時(shí)候就能排除一行军拟，所以無(wú)論情況怎么樣剃执，都能使下一次尋找的矩陣范圍變小，而左上角和右下角的數(shù)是做不到的吻谋，所以我們可以從左下和右上出發(fā)忠蝗。
時(shí)間復(fù)雜度：顯然O(M+N)
空間復(fù)雜度：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
}
