【剑指offer】面试题4：二维数组中的查找

小鱼儿 2022-04-01 11:59 145阅读 0赞

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

规律：

1.  首先选取数组中右上角的数字。
2.  如果该数字等于要查找的数字，查找过程结束。
3.  如果该数字大于要查找的数字，剔除这个数字所在的列；
4.  如果该数字小于要查找的数字，剔除这个数字所在的行。

也就是说如果要查找的数字不在数组的右上角，则每一次都在数组的查找范围中剔除行或者列，这样每一步都可以缩小查找范围，直到要查找的数字，或者查找范围为空。

public class FindNumAtMatrix {
    
    	public static boolean find(int[][] arr, int number){
    		
    		if(arr == null){
    			return false;
    		}
    		
    		// 选取数组查找范围内的右上角数字
    		int column = arr[0].length - 1;   // 列号
    		int row = 0;                      // 行号
    		
    		while(row < arr.length && column >= 0){
    			if(arr[row][column] == number){
    				return true;
    			}else if(arr[row][column] > number){
    				// 如果当前数小于查找范围的右上角元素时，
    				// 则说明它在查找范围的左边，删除当前列
    				column--;
    			}else{
    				// 如果当前数大于查找范围的右上角元素时，
    				// 则说明它在查找范围的下边，删除当前行
    				row++;
    			}
    		}
    		return false;
    	}
    	
    	public static void main(String[] args) {
    		int[][] array = new int[4][4];
    		array[0][0] = 1;
    		array[0][1] = 2;
    		array[0][2] = 8;
    		array[0][3] = 9;
    		array[1][0] = 2;
    		array[1][1] = 4;
    		array[1][2] = 9;
    		array[1][3] = 12;
    		array[2][0] = 4;
    		array[2][1] = 7;
    		array[2][2] = 10;
    		array[2][3] = 13;
    		array[3][0] = 6;
    		array[3][1] = 8;
    		array[3][2] = 11;
    		array[3][3] = 15;
    		System.out.println(find(array,6));
    	}
    }

本题中每次选取的是二维数组中的可查找范围中的右上角元素，其实也可以选择左下角元素，道理相同，每次比较如果不相等，则可以剔除当前行或者当前列，因此不可以选择左上角或者右下角元素，因为它们是可查找范围中的最小值或者最大值，经过比较，既不能剔除当前行也不能剔除当前列。