題目

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

樣例

輸入數(shù)組： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ]如果輸入查找數(shù)值為7，則返回true， 如果輸入查找數(shù)值為5，則返回false。

方法一：

(單調(diào)性掃描) O(n+m)O(n+m)
核心在于發(fā)現(xiàn)每個(gè)子矩陣右上角的數(shù)的性質(zhì)：

如下圖所示，x左邊的數(shù)都小于等于x，x下邊的數(shù)都大于等于x

因此我們可以從整個(gè)矩陣的右上角開始枚舉，假設(shè)當(dāng)前枚舉的數(shù)是 xx：

如果 xx 等于target，則說明我們找到了目標(biāo)值，返回true；
如果 xx 小于target，則 xx 左邊的數(shù)一定都小于target，我們可以直接排除當(dāng)前一整行的數(shù)；
如果 xx 大于target，則 xx 下邊的數(shù)一定都大于target，我們可以直接排序當(dāng)前一整列的數(shù)；
排除一整行就是讓枚舉的點(diǎn)的橫坐標(biāo)加一，排除一整列就是讓縱坐標(biāo)減一。
當(dāng)我們排除完整個(gè)矩陣后仍沒有找到目標(biāo)值時(shí)，就說明目標(biāo)值不存在，返回false。

時(shí)間復(fù)雜度分析
每一步會(huì)排除一行或者一列，矩陣一共有 nn 行，mm 列，所以最多會(huì)進(jìn)行 n+mn+m 步。所以時(shí)間復(fù)雜度是 O(n+m)O(n+m)。

作者：yxc 鏈接：https://www.acwing.com/solution/AcWing/content/702/ 來源：AcWing 著作權(quán)歸作者所有。商業(yè)轉(zhuǎn)載請聯(lián)系作者獲得授權(quán)，非商業(yè)轉(zhuǎn)載請注明出處。 class Solution { public:bool searchArray(vector<vector<int>> array, int target) {if (array.empty() || array[0].empty()) return false;int n=array[0].size(),m=array.size();int i=0, j=n;while(j>=0 || i<m) {if(array[i][j] > target) j--; //在左邊，則列--if(array[i][j] < target) i++; //在右邊，則行++return true;}return false;} };

心得

記住這個(gè)矩陣的形狀即可

總結(jié)

以上是生活随笔為你收集整理的AcWing之二维数组的查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。