劍指offer 01. 二維數(shù)組中的查找
前言
牛客網(wǎng)劍指 offer 的 66 道題，基本屬于必刷題，帥地打算把 66 道的題解大致過一遍，大家也可以跟著帥地，每日一道刷起來！每道題會提供簡單的思路以及測試通過的代碼。
問題描述
在一個二維數(shù)組中（每個一維數(shù)組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)，判斷數(shù)組中是否含有該整數(shù)。
[
]
給定 target = 7，返回 true。
給定 target = 3，返回 false。
示例1
輸入：7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：true
說明：存在7，返回true
示例2
輸入：3,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值：false
說明：不存在3，返回false
題目鏈接：https://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e?tpId=13
解答思路
一種簡單的方法就是整個數(shù)組都遍歷，當然，數(shù)組從左到右，從上到下都是有序的，如果你遍歷整個數(shù)組的話，那就浪費了數(shù)組的局部有序性了。
如果我們從 row = 0 和col = 0開始遍歷的話，發(fā)現(xiàn)右邊的數(shù)比 array[row] [col] 大，而下邊也比 array[row] [col]大，這樣的話，貌似局部有序性沒有派上用場
遍歷不一定就一定要從 row = 0 和 col = 0開始，有時候，換個角度，一切就豁然開朗了。
實際上我們從數(shù)組的左下角開始遍歷的話
1、如果array[row] [col] > target，那么 target 必定在元素 array[row] [col] 所在列的上邊，則往上移動。
2、如果 array[row] [col] < target，那么target必定在元素 array[row] [col] 所在行的右邊，則往右移動。
3、否則找到目的數(shù)。
這樣，就完美利用到局部有序性了。代碼如下：
public class Solution {
public boolean Find(int target, int [][] array) {
if(array == null)return false;
int row = array.length - 1;
int col = array[0].length - 1;
int j = 0;
while (row >= 0 && j <= col) {
if (array[row][j] > target) {
row--;
} else if (array[row][j] < target) {
j++;
} else {
return true;
}
}
return false;
}
}
此種方法對時間復雜度是O(m + n)，（m和n表示數(shù)組的長度和寬度）
當然，這里還有另外一種方法，因為每一行都是有序的，就是對每一行進行二分查找，這種方法的話，時間復雜度是 O(nlogm)，這種方法就不提供代碼了。
另外，所有題解及其代碼，都會同步到帥地的個人網(wǎng)站，這樣閱讀起來會舒服一些，方便大家學習，鏈接：https://www.iamshuaidi.com/1343.html
PS：點擊閱讀原文即可直達，推薦 PC 端打開。