在一个 n * m 的二维数组中，每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
示例:
现有矩阵 matrix 如下：
[ [1, 4, 7, 11, 15], [2, 5, 8, 12, 19], [3, 6, 9, 16, 22], [10, 13, 14, 17, 24], [18, 21, 23, 26, 30] ]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
限制：
0 <= n <= 1000
0 <= m <= 1000
题解：
从右上角开始走，利用这个顺序关系可以在O(m+n)的复杂度下解决这个题：
- 如果当前位置元素比target小，则row++
- 如果当前位置元素比target大，则col--
- 如果相等，返回true
- 如果越界了还没找到，说明不存在，返回false
1 public class Problem04 { 2 public static void main(String[] args) { 3 4 int array[][] = {{1, 4, 7, 11, 15}, 5 {2, 5, 8, 12, 19}, 6 {3, 6, 9, 16, 22}, 7 {10, 13, 14, 17, 24}, 8 {18, 21, 23, 26, 30}}; 9 /*System.out.println(array.length); 10 System.out.println(array[0].length);*/ 11 12 13 System.out.println(find3(array,1)); 14 15 16 } 17 18 public static boolean find1(int arr[][], int number) { 19 //直接暴力遍历，但是没有使用题目的递增条件，时间0(m*n) 20 int row=arr.length; 21 for (int i = 0; i < row; i++) { 22 for (int j = 0; j < arr[i].length; j++) { 23 if(arr[i][j]==number) 24 return true; 25 } 26 } 27 return false; 28 } 29 30 public static boolean find2(int arr[][], int number) { 31 //将右上角看作二叉搜索树，时间0(m+n),注意数组为null或者数组为空的情况 32 if (arr == null || arr.length == 0) 33 return false; 34 35 int rows = 0; 36 int line = arr[0].length - 1; 37 while (arr[rows][line] != number) { 38 39 if (number > arr[rows][line]) { 40 rows++; 41 if (rows == arr.length - 1) 42 return false; 43 }else{ 44 line--; 45 if (line < 0) 46 return false; 47 } 48 } 49 return true; 50 } 51 public static boolean find3(int arr[][], int number) { 52 //将右上角看作二叉搜索树，时间0(m+n),注意数组为null或者数组为空的情况 53 int rows = 0; 54 int line = arr[0].length - 1; 55 56 if (arr == null || arr.length == 0||arr[0].length==0) 57 return false; 58 59 while (rows<arr.length&&line>=0) {//此处是且 60 61 if (number > arr[rows][line]) { 62 rows++; 63 }else if(number<arr[rows][line]){ 64 line--; 65 }else{ 66 return true; 67 } 68 } 69 return false; 70 71 } 72 73 }
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-wei-shu-zu-zhong-de-cha-zhao-lcof