剑指offer_牛客_JZ1——二维数组中的查找

题目描述

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例1

输入

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

返回值

true

思路

(旨在拓宽思路，并非标答)
这道题目里涉及的矩阵名为杨氏矩阵，杨氏矩阵的查找是非常经典的问题。

方法一：暴力

剑指offer很多题都存在数据弱的问题，下表是暴力花的时间。

方法二：二分+递归

1. 二分知识点的复习

在一维数组里查找某个数，如果数组有序，那么可以采用二分的方法：

#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. 二分能否运用到这道题里面

虽然二维数组从上到下，从左到右都是有序的，但是当一个pos确认比tar大的时候，我们只能排除它右下角的数据，显然不能直接使用二分查找。在借鉴了其他的思路后，我思考着能否将二分也套用进去。

原思路

原解题思路的具体过程可以参照牛客的官方题解。

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;
};

二分优化版

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;
    }
};

不过这样的写法在牛客上和原思路花了一样的时间，不知道是不是我的写法有问题，欢迎探讨。