前言

?？途W(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ù)組都遍歷，當(dāng)然，數(shù)組從左到右，從上到下都是有序的，如果你遍歷整個數(shù)組的話，那就浪費(fèi)了數(shù)組的局部有序性了。

如果我們從 row = 0 和col = 0開始遍歷的話，發(fā)現(xiàn)右邊的數(shù)比 array[row] [col] 大，而下邊也比 array[row] [col]大，這樣的話，貌似局部有序性沒有派上用場

遍歷不一定就一定要從 row = 0 和 col = 0開始，有時候，換個角度，一切就豁然開朗了。

實(shí)際上我們從數(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;
    }
}

此種方法對時間復(fù)雜度是O(m + n)，（m和n表示數(shù)組的長度和寬度）

當(dāng)然，這里還有另外一種方法，因?yàn)槊恳恍卸际怯行虻?，就是對每一行進(jìn)行二分查找，這種方法的話，時間復(fù)雜度是 O(nlogm)，這種方法就不提供代碼了。

另外，所有題解及其代碼，都會同步到帥地的個人網(wǎng)站，這樣閱讀起來會舒服一些，方便大家學(xué)習(xí)，鏈接：https://www.iamshuaidi.com/1343.html

PS：點(diǎn)擊閱讀原文即可直達(dá)，推薦 PC 端打開。