[Offer] [4] [Search in two-dimensional arrays]

Topic Description

In a two-dimensional array, each row is sorted in increasing order from left to right, and each column is sorted in increasing order from top to bottom. Please complete a function, input such a two-dimensional array and an integer, to determine whether the array contains the integer.

Thought analysis

Since a given two-digit array is increasing from left to right and from top to bottom, it is possible to select a corner (upper right corner or lower left corner) in a two-dimensional array to start searching and filtering. For example, starting from the upper right corner, if the target number is larger than the number in the upper right corner (due to increasing from left to right), it means that the number to be searched is below the first line, then the first line. The number of rows can be excluded. If you continue to search in this way, you can sort out the target number.

Java code

public class Offer004 {
    public static void main(String[] args) {
//      int [][] arr = {{},{}}; 
        int [][] arr = {{1,2,8,9},{2,4,9,12},{4,7,10,13},{6,8,11,15}}; 
//      System.out.println(arr.length);
//      System.out.println(arr[0].length);
        System.out.println(Offer004.findInPartiallySortedMatrix(arr, 11));
        System.out.println(Offer004.findInPartiallySortedMatrix(arr, 7));
    }
    public static boolean findInPartiallySortedMatrix(int[][] arr, int target) {
        return Solution1(arr, target);
    }
    
    /**
     * Starting from the upper right corner, if the target number is less than the upper right corner number, j--, greater than i++, narrow the search scope in turn.
     *              
     * @param arr
     * @param target
     * @return
     */
    public static boolean Solution1(int[][] arr, int target) {
        if(arr==null || arr.length<=0 || arr[0].length<=0 ) {
            throw new IllegalArgumentException("invalid parameter!");
        }   
        int i=0;
        int j= arr[0].length-1;
        while(i<arr.length && j>=0) {
            if(target<arr[i][j]) {
                j--;
            }else if(target>arr[i][j]){
                i++;
            }else {
                return true;
            }
        }   
        return false;
    }
}

Code Links

Sword Finger Office Code - Java

Tags: PHP Java less

Posted on Wed, 09 Oct 2019 15:35:55 -0700 by pdn