二维数组中的查找

在一个二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

样例 输入数组： [ [1,2,8,9]， [2,4,9,12]， [4,7,10,13]， [6,8,11,15] ] 如果输入查找数值为7，则返回true， 如果输入查找数值为5，则返回false。

暴力破解

时间复杂度O(n * m)

class Solution { public boolean searchArray(int[][] array, int target) { for(int i = 0;i < array.length; i++){ for(int j = 0;j < array[i].length;j++){ if(array[i][j] > target){ break; } if(array[i][j] == target){ return true; } } } return false; } }

进阶版

因此我们可以从整个矩阵的右上角开始枚举，假设当前枚举的数是 nm：

如果 nm等于target，返回true； 如果 nm小于target，则 xx 左边的数都小于target，我们排除当前行； 如果 nm大于target，则 xx 下边的数都大于target，我们排序当前列；

时间复杂度O(n + m) 因为每次判断完会少一行或少一列，最多是少n行和m列，所以是O(n+m)

public class Solution { boolean searchArray(int[][] array, int target) { if(array == null || array.length == 0 || array[0].length == 0) { return false; } int i = 0, j = array[0].length - 1; while(i < array.length && j >= 0) { if(array[i][j] == target) { return true; } if(array[i][j] > target) { j --; } else { i ++; } } return false; } };