題目描述

給定一個二維數(shù)組，其每一行從左到右遞增排序，從上到下也是遞增排序。給定一個數(shù)，判斷這個數(shù)是否在該二維數(shù)組中。

Consider the following matrix:
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.
Given target = 20, return false.

解題思路

要求時間復雜度 O(M + N)，空間復雜度 O(1)。其中 M 為行數(shù)，N 為 列數(shù)。

該二維數(shù)組中的一個數(shù)，小于它的數(shù)一定在其左邊，大于它的數(shù)一定在其下邊。因此，從右上角開始查找，就可以根據(jù) target 和當前元素的大小關(guān)系來縮小查找區(qū)間，當前元素的查找區(qū)間為左下角的所有元素。

我的代碼

package arithmetic.mydatabase.day01.arithmetic04;

/*
        給定一個二維數(shù)組，其每一行從左到右遞增排序，從上到下也是遞增排序。
        給定一個數(shù)，判斷這個數(shù)是否在該二維數(shù)組中。

                Consider the following matrix:
                [
                [1,   4,  7, 11, 15],
                [2,   5,  8, 12, 19],
                [3,   6,  9, 16, 22],
                [10, 13, 14, 17, 24],
                [18, 21, 23, 26, 30]
                ]

                Given target = 5, return true.
                Given target = 20, return false.

                要求時間復雜度 O(M + N)，空間復雜度 O(1)。其中 M 為行數(shù)，N 為 列數(shù)。

                該二維數(shù)組中的一個數(shù)，小于它的數(shù)一定在其左邊，大于它的數(shù)一定在其下邊。
                因此，從右上角開始查找，就可以根據(jù) target 和當前元素的大小關(guān)系來縮小查找區(qū)間，當前元素的查找區(qū)間為左下角的所有元素。
*/

public class Test {
    public static void main(String[] args) {
        int a[][] = {
                {1,  4,  7,  11, 15},
                {2,  5,  8,  12, 19},
                {3,  6,  9,  16, 22},
                {10, 13, 14, 17, 24},
                {18, 21, 23, 26, 30}
                };

        for (int[] x :a){
            for (int y:x){
                System.out.print(y+" ");
            }
            System.out.println();
        }

        int i=5;

        Test test = new Test();
        boolean find = test.Find(i, a);
        System.out.println(find);

    }

    public boolean Find(int target,int [][] matrix){
        if (matrix==null || matrix.length ==0|| matrix[0].length==0)//可行性判斷
            return false;

        int rows = matrix.length;//行
        int cols = matrix[0].length; //列

//        我們從右上角開始
        int r=0,c=cols-1;

        while ( r<=cols-1 && c>=0 ){//可行性判斷

            if (target == matrix[r][c])
                return true;
            else if (target > matrix[r][c])
                r++;
            else
                c--;
        }
        return false;
    }

}

我的做題思路
如解題思路
數(shù)據(jù)從左至右增大，從上到下增大，如果我們需要找到一個數(shù)是否是在該數(shù)組中，我們就需要與右上角的數(shù)據(jù)比較，如果比該數(shù)大，我們的行下標+1否則列下標-1，以此類推如果有沖突（即是移動比較的數(shù)組后發(fā)現(xiàn)下標回退為上一個數(shù)據(jù)，說明數(shù)組中沒有我們需要的數(shù)據(jù)）

進數(shù)據(jù)后我們先進行可行性判斷

    if (matrix==null || matrix.length ==0|| matrix[0].length==0)//可行性判斷 驗證該數(shù)組是否真實存在

然后我們進行標注，標注該二維數(shù)組的行和列

int rows = matrix.length;//行
int cols = matrix[0].length;//列

此時，我們從右上角開始
即是

    int r=0,c=cols-1;

然后我們進行可行性判斷（防止數(shù)組下標越界）

    while ( r<=cols-1 && c>=0 ){//可行性判斷

如果 我們設(shè)定的值和數(shù)組中當前的值相同
我們返回true

        if (target == matrix[r][c])
            return true;

如果我們設(shè)定的值比數(shù)組當前的值大
此時行數(shù)+1 繼續(xù)循環(huán)

        else if (target > matrix[r][c])
            r++;

如果我們設(shè)定的值比數(shù)組當前的值小
此時列數(shù)-1 繼續(xù)循環(huán)

        else
            c--;

如果都沒有找到則返回為false