在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個(gè)高效的函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

示例

現(xiàn)有矩陣 matrix 如下：

[

[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

方法一：暴力

如果不考慮二維數(shù)組排好序的特點(diǎn)，則直接遍歷整個(gè)二維數(shù)組的每一個(gè)元素，判斷目標(biāo)值是否在二維數(shù)組中存在。

依次遍歷二維數(shù)組的每一行和每一列。如果找到一個(gè)元素等于目標(biāo)值，則返回 true。如果遍歷完畢仍未找到等于目標(biāo)值的元素，則返回 false。

代碼

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(nm)。二維數(shù)組中的每個(gè)元素都被遍歷，因此時(shí)間復(fù)雜度為二維數(shù)組的大小。

• 空間復(fù)雜度：O(1)。

方法二：線性查找

由于給定的二維數(shù)組具備每行從左到右遞增以及每列從上到下遞增的特點(diǎn)，當(dāng)訪問到一個(gè)元素時(shí)，可以排除數(shù)組中的部分元素。

從二維數(shù)組的右上角開始查找。如果當(dāng)前元素等于目標(biāo)值，則返回 true。如果當(dāng)前元素大于目標(biāo)值，則移到左邊一列。如果當(dāng)前元素小于目標(biāo)值，則移到下邊一行。

可以證明這種方法不會錯(cuò)過目標(biāo)值。如果當(dāng)前元素大于目標(biāo)值，說明當(dāng)前元素的下邊的所有元素都一定大于目標(biāo)值，因此往下查找不可能找到目標(biāo)值，往左查找可能找到目標(biāo)值。如果當(dāng)前元素小于目標(biāo)值，說明當(dāng)前元素的左邊的所有元素都一定小于目標(biāo)值，因此往左查找不可能找到目標(biāo)值，往下查找可能找到目標(biāo)值。

• 若數(shù)組為空，返回 false

• 初始化行下標(biāo)為 0，列下標(biāo)為二維數(shù)組的列數(shù)減 1

• 重復(fù)下列步驟，直到行下標(biāo)或列下標(biāo)超出邊界

• 獲得當(dāng)前下標(biāo)位置的元素 num

• 如果 num 和 target 相等，返回 true

• 如果 num 大于 target，列下標(biāo)減 1

• 如果 num 小于 target，行下標(biāo)加 1

• 循環(huán)體執(zhí)行完畢仍未找到元素等于 target ，說明不存在這樣的元素，返回 false

復(fù)雜度分析

• 時(shí)間復(fù)雜度：O(n+m)。訪問到的下標(biāo)的行最多增加 n 次，列最多減少 m 次，因此循環(huán)體最多執(zhí)行 n + m 次。

• 空間復(fù)雜度：O(1)。

寫在最后

本文內(nèi)容出處是力扣官網(wǎng)，希望和大家一起刷算法，在后面的路上不變禿但是變強(qiáng)！

好兄弟可以點(diǎn)贊并關(guān)注我的公眾號“javaAnswer”，全部都是干貨。