NxN的數組矩陣,每一行,列均從左到右,從上之下遞增。

一、問題

NxN的數組矩陣,每一行,列均從左到右,從上之下遞增。

确定一個數x是否在該矩陣内。

二、解決代碼

public static void main(String[] args) {
        Scanner scanner=new Scanner(System.in);
        /*System.out.println("請輸入數字N");
        int n=scanner.nextInt();
        int a[][]=new int[n][n];
        System.out.println("請逐行輸入資料");
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                a[i][j]=scanner.nextInt();
            }
        }*/
        int a[][]=new int[][]{
                {,,,},
                {,,,},
                {,,,},
                {,,,}
        };
        System.out.println("請輸入你要查找的元素x");
        int x=scanner.nextInt();
        search(a, x);
    }

    private static void search(int[][] a, int k) {
        int m = a.length;
        int n = a[].length;
        for(int i = , j = n-; j >=  && i < n; ){
            if(a[i][j] == k){
                System.out.println(true);
                return;
            }else if(a[i][j] < k){
                i++;
            }else{
                j--;
            }
        }
        System.out.println(false);
    }
           

三、分析

因為矩陣是從左到右,從上到下遞增的,從矩陣的右上角開始,而右上角是第一行的最大值,如果目前元素小于要找的數x,說明改行不可能存在x,因為每一行中,第n-1列是該行最大值,是以就到下一行(i++),如果a[i] [j]大于要找的數,則說明該數存于這一行中,進行j–操作,因為此時的a[i] [j]是該列中最小的值了,不能再向下移動了。

Patience and perseverance will get paid.