題目：二維數(shù)組中的查找

在一個(gè) n * m 的二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(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 <= 10000 <= m <= 1000

---

解題思路：

首先選取二維數(shù)組當(dāng)中右上角的數(shù)字。

• 如果該數(shù)字等于target，則查找過(guò)程結(jié)束；
• 如果該數(shù)字大于target，則剔除這個(gè)數(shù)字的所在列（由于該列是遞增順序，這個(gè)數(shù)字是這一列里的最小的數(shù)字，這一列的數(shù)字都會(huì)比target大）；
• 如果該數(shù)字小于target，則剔除這個(gè)數(shù)字的所在行（同理，這個(gè)數(shù)字是這一行里最大的數(shù)字，所以這一行的數(shù)字都要比target小）；
• 再次選取剩余區(qū)域的右上角的數(shù)字，然后重復(fù)上述的過(guò)程。

時(shí)間復(fù)雜度O(m+n)(其中 m?和 n 分別代表行數(shù)和列數(shù))，空間復(fù)雜度O(1)

class Solution {
public:bool findNumberIn2DArray(vector<vector<auto>>& matrix, auto target) {auto rows = matrix.size();auto columns = matrix[0].size();if(rows>0 && columns>0){    auto row = 0 ;auto column = columns-1;while(row<rows&&column>=0){if(matrix[row][column]==target) {return true;}else if(matrix[row][column]>target) {column--;}else row++;}}return false;}
};

LeetCode代碼提交報(bào)錯(cuò)：

reference binding to null pointer of type 'struct value_type'

后來(lái)找到問(wèn)題是，測(cè)試用例如果直接給出一個(gè)空字符串的話，也就是說(shuō)函數(shù)傳進(jìn)的是一個(gè)空的vector容器，那么在調(diào)用matrix[0]的時(shí)候就會(huì)下標(biāo)越界，因?yàn)閙atrix[0]是不存在的。加上如下判斷條件之后，順利通過(guò)。

if(matrix.empty())  //不加這個(gè)傳入為空的判斷的話會(huì)訪問(wèn)越界return false;

class Solution {
public:bool findNumberIn2DArray(vector<vector<auto>>& matrix, auto target) {if(matrix.empty())  //不加這個(gè)傳入為空的判斷的話會(huì)訪問(wèn)越界return false;auto rows = matrix.size();auto columns = matrix[0].size();if(rows>0 && columns>0){    auto row = 0 ;auto column = columns-1;while(row<rows&&column>=0){if(matrix[row][column]==target) {return true;}else if(matrix[row][column]>target) {column--;}else row++;}}return false;}
};

?

總結(jié)

以上是生活随笔為你收集整理的剑指offer：面试题04. 二维数组中的查找的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

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