题目描述

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

解题思路

        因为二维数组是有序的，所以我的思路是选择一个特殊的起始位置，使得他对任意方向有着绝对的判断。我选择的位置是左下角的位置，满足了他的正上方的数字绝对比他小且他的正右方的数字绝对比他大。那么此时我将target与这个数相比，比这个数大就可以删掉他所在的一整列，然后再与右边相邻的数进行比较，比这个数小就可以删掉他所在的一整行，然后再与上边相邻的数进行比较。所以最大时间复杂度只有O(m+n)

代码 

public class Solution {
    public static void main(String[] args){
        Solution solution = new Solution();
        int[][] arr = new int[][]{{1,2},{3,4}};
        System.out.println(solution.Find(2,arr));
    }
    public boolean Find(int target, int [][] array) {//左下角开始找
        if (array == null || array.length == 0 || (array.length == 1 && array[0].length == 0)) 
            return false;
        int arrayRow = array.length - 1;
        int arrayLine = 0;
        while(arrayRow >= 0 && arrayLine <= array[0].length - 1){
            if(target > array[arrayRow][arrayLine]){
                arrayLine++;
            }else if(target < array[arrayRow][arrayLine]){
                arrayRow--;
            }else{
                return true;
            }
        }
        return false;
    }
}