題目：

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

來源：力扣（LeetCode）
鏈接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof
著作權歸領扣網絡所有。商業轉載請聯系官方授權，非商業轉載請注明出處。

示例：

?

解答思路：

面對這樣的問題第一反應是暴力搜索吧！使用兩個循環遍歷每個元素，這樣的話時間復雜度就是O(N*M)。思考一秒鐘這肯定不是最優的，開始發現規律，左上角的元素是最小的，右下角的元素是最大的，右上角和左下角的元素在某個方向上最大，在另一個方向最小。具體的實現思路下面再說。

• C++解答思路：

拿到題經過思考以后，想到了使用vector中的find函數在每一行中搜索元素，在不考慮vector的find函數的時間復雜度下，該方法的時間復雜度為O(N)。

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {int flag = -1;if(matrix.size() == 0){return false;}for (auto mat:matrix){if (find(mat.begin(),mat.end(),target) != mat.end()){flag = 1;break;}else{flag = 0;continue;}}if(flag){return true;}else{return false;}}

根據左下角和右上角元素的特性，假設從右上角開始搜索，然后根據大小決定向大的方向或者向小的方向移動。

bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {int rows = matrix.size();if (rows==0){return false;}int cols = matrix.at(0).size();if(cols == 0){return false;}int row = rows-1,col = 0,flag = 0;while (row >= 0 && col < cols){int val = matrix.at(row).at(col);if(val < target){col += 1;}else if(val > target){row -= 1;}else{flag = 1;break;}}if (flag){return true;}else{return false;}}

兩種方法的用時都為24ms

• python解答思路：

python的解答思路和C++第二種一樣。

def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:row,col = len(matrix) - 1,0flag = 0while row >= 0 and col < len(matrix[0]):val = matrix[row][col]if val > target:row -= 1elif val < target:col += 1elif val == target:flag = 1breakif flag:return Trueelse:return False

總結

以上是生活随笔為你收集整理的leetcode:剑指offer----二维数组中查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。