題目描述

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

示例1

輸入

7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]

返回值

true

思路

(旨在拓寬思路，并非標(biāo)答)
這道題目里涉及的矩陣名為楊氏矩陣，楊氏矩陣的查找是非常經(jīng)典的問題。

方法一：暴力

劍指offer很多題都存在數(shù)據(jù)弱的問題，下表是暴力花的時間。

方法二：二分+遞歸

1. 二分知識點的復(fù)習(xí)

在一維數(shù)組里查找某個數(shù)，如果數(shù)組有序，那么可以采用二分的方法：

#include <iostream>
using namespace std;

int BiSearch(int arr[],int target,int size){
    int l=0,r=size-1;
    while(l<=r){
        int mid = (l+r)/2;
        if(arr[mid]==target) return mid;
        else if(arr[mid]>target) r = mid-1;
        else l = mid+1;
    }
    return -1;
}

int main(){
    int arr[10] = {0,1,2,3,4,5,6,7,8,9};
    int target = 2;
    cout<<BiSearch(arr,target,10)<<endl;
    return 0;
}

2. 二分能否運用到這道題里面

雖然二維數(shù)組從上到下，從左到右都是有序的，但是當(dāng)一個pos確認(rèn)比tar大的時候，我們只能排除它右下角的數(shù)據(jù)，顯然不能直接使用二分查找。在借鑒了其他的思路后，我思考著能否將二分也套用進(jìn)去。

原思路

原解題思路的具體過程可以參照牛客的官方題解。

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        this->height = int(array.size());
        if(height==0) return false;
        this->width = int(array[0].size());
        int i=height-1,j=0;
        while(i>=0&&j<width){
            if(array[i][j]==target) return true;
            else if(array[i][j]>target) i--;
            else j++;
        }
        return false;
    }
private:
    int height;
    int width;
};

二分優(yōu)化版

class Solution {
public:
    bool Find(int target, vector<vector<int> > array) {
        int height = int(array.size());
        if(height==0) return false;
        int width = int(array[0].size());
        int li=height-1,ri=0,lj=0,rj=width-1;
        int i=li,j=lj;
        while(i>=0&&j<width){
            if(array[i][j]==target) return true;
            else if(array[i][j]>target){
                while(li>=ri){
                    int mid = (li+ri)/2;
                    if(array[mid][j]==target) return true;
                    else if(array[mid][j]<target) ri = mid+1;
                    else li = mid-1;
                }
                i = li;
                ri = 0;
            }
            else{
                while(lj<=rj){
                    int mid = (lj+rj)/2;
                    if(array[i][mid]==target) return true;
                    else if(array[i][mid]>target) rj = mid-1;
                    else lj = mid+1;
                }
                j = lj;
                rj = width-1;
            }
        }
        return false;
    }
};

不過這樣的寫法在?？蜕虾驮悸坊艘粯拥臅r間，不知道是不是我的寫法有問題，歡迎探討。