【剑指offer】二维数组中的查找
题目描述
在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
样例
输入数组：
[
[1,2,8,9]，
[2,4,9,12]，
[4,7,10,13]，
[6,8,11,15]
]
如果输入查找数值为7，则返回true，如果输入查找数值为5，则返回false。
思路一：暴力法
1
2 public class Solution {
3 public static void main(String[] args) {
4 int[][] matrix = {
5 {1, 2, 8, 9},
6 {2, 4, 9, 12},
7 {4, 7, 10, 13},
8 {6, 8, 11, 15},
9 };
10 //测试11是否在数组中
11 System.out.println("测试1："+Find(11,matrix));
12 //测试20是否在数组中
13 System.out.println("测试2："+Find(20,matrix));
14 //测试空数组
15 System.out.println("测试3："+Find(20,null));
16 }
17 public static boolean Find(int target, int [][] array) {
18 //思路1:遍历全数组，时间复杂度O(n^2)
19 if(array==null||array.length==0||array[0].length==0) {//测试空数组,array==null必须在前面！
20 return false;
21 }
22 //获取array数组的行数和列数
23 int row = array.length;//length长度从1开始；补充：二维数组实质是一维数组，一维数组包含子数组就形成了二级！
24 int col = array[0].length;//获取第一行的长度，即列，length长度从1开始
25 for(int i =0;i<row;i++) {
26 for(int j = 0;j<col;j++) {
27 if(array[i][j]==target) {
28 return true;
29 }
30 }
31 }
32 return false;//没找到，返回false
33 }
34 }
思路二：找规律
代码：
1 package cn.jnu.ma01;
2
3 public class Solution {
4 public static void main(String[] args) {
5 int[][] matrix = {
6 {1, 2, 8, 9},
7 {2, 4, 9, 12},
8 {4, 7, 10, 13},
9 {6, 8, 11, 15},
10 };
11 //测试11是否在数组中
12 System.out.println("测试1："+Find(11,matrix));
13 //测试20是否在数组中
14 System.out.println("测试2："+Find(20,matrix));
15 //测试空数组
16 System.out.println("测试3："+Find(20,null));
17 }
18 public static boolean Find(int target, int [][] array) {
19
20 //int rows = array.length,不写在这因为，array可能为空。int rows = array.length会报错。所以先测试array为不为空
21 if(array==null||array.length==0||array[0].length==0) {//测试空数组,array==null必须在前面！
22 return false;
23 }
24 //获取array数组的行数和列数
25 int rows = array.length;//length长度从1开始；补充：二维数组实质是一维数组，一维数组包含子数组就形成了二级！
26 int cols = array[0].length;//获取第一行的长度，即列，length长度从1开始
27
28 int row=0;
29 int col=cols-1;//获取第一行的长度，即列，length长度从1开始;col为下标，范围为[0,cols-1];
30 while(row<rows&&col>=0) {
31 if(target==array[row][col])
32 {
33 return true;
34 }
35 if(target>array[row][col]) {
36 row++;
37 }else { //target<array[row][col]
38 col--;
39 }
40 }
41 return false;//没找到，返回false
42 }
43 }
测试1：true
测试2：false
测试3：false
思路三：左下角
代码：
1 package cn.jnu.ma01;
2
3 public class Demo {
4 public static void main(String[] args) {
5 int[][] matrix = {
6 {1, 2, 8, 9},
7 {2, 4, 9, 12},
8 {4, 7, 10, 13},
9 {6, 8, 11, 15},
10 };
11 //测试11是否在数组中
12 System.out.println("测试1："+Find(11,matrix));
13 //测试20是否在数组中
14 System.out.println("测试2："+Find(20,matrix));
15 //测试空数组
16 System.out.println("测试3："+Find(20,null));
17 }
18 public static boolean Find(int target, int [][] array) {
19
20 // int rows = array.length,不写在这因为，array可能为空。int rows = array.length会报错。所以先测试array为不为空
21 if(array==null||array.length==0||array[0].length==0) {//测试空数组,array==null必须在前面！
22 return false;
23 }
24 //获取array数组的行数和列数
25 int rows = array.length;//length长度从1开始；补充：二维数组实质是一维数组，一维数组包含子数组就形成了二级！
26 int cols = array[0].length;//获取第一行的长度，即列，length长度从1开始
27
28 int row=rows-1;
29 int col=0;//获取第一行的长度，即列，length长度从1开始;col为下标，范围为[0,cols-1];
30 while(col<cols&&row>=0) {
31 if(target==array[row][col])
32 {
33 return true;
34 }
35 if(target>array[row][col]) {
36 col++;
37 }else { //target<array[row][col]
38 row--;
39 }
40 }
41 return false;//没找到，返回false
42 }
43
44 }
思考：为什么不选择左上角或者右下角
下载：