劍指offer編程題Java實現——面試題3二維數組中的查找

題目描述

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

下面是我實現的代碼，修改下類名(Solution)和方法名(Find)通過了牛客網的測試用例

public class No2Array{
    public static void main(String[] args){
        int[][] array={{1,2,8,9},
                    {2,4,9,12},
                    {4,7,10,13},
                    {6,8,11,15}};
        System.out.println(findByTheUpperRightCorner(5,array));
        System.out.println(findByTheLowerLeftCorner(7,array));
    }
    
    /*
     * 選取數組查找范圍內的右上角的數字，如果該數字等于要查找的數字，則查找結束。
     * 如果該數字小于要查找的數字，則剔除該數字所在的行；
     * 如果該數字大于要查找的數字，則剔除該數字所在的列；
     */
    public static boolean findByTheUpperRightCorner(int target, int [][] array) {
        if(array.length>0){
            int    rows=array.length;
            int columns=array[0].length;
            int row=0;
            int column=columns-1;
            while(row<rows&&column>=0){
                if(array[row][column]==target)
                    return true;
                if(array[row][column]>target)
                    column--;
                else
                    row++;
            }
            return false;
        }
        return false;
    }
    
    /*
     * 選取數組查找范圍內的左下角的數字，如果該數字等于要查找的數字，則查找結束；
     * 如果該數字小于要查找的數字，則剔除該數字所在的列；
     * 如果該數字大于要查找的數字，則剔除該數字所在的行；
     */
    public static boolean findByTheLowerLeftCorner(int target,int[][] array){
        if(array.length>0){
            int rows=array.length;
            int columns=array[0].length;
            int row=rows-1;
            int column=0;
            while(row>=0&&column<columns){
                if(array[row][column]==target)
                    return true;
                if(array[row][column]<target)
                    column++;
                else
                    row--;
            }
            return false;
        }
        return false;
    }
}

通過選取右上角和左上角的兩種實現思路都給出了實現代碼，明白其中一個原理另外一個也就很容易了。關鍵是不能選取左上角或者右下角的數組作為對比，比如選取左上角的數字小于查找的值，那么該數字的下面數字和右面數字都有可能是要查找的范圍，這樣無法縮小查找范圍。所以只要知道從右上角或者左下角進行查找就很容易解決了。