剑指offer--二维数组中的查找

发表于 | 分类于 |

题意：

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

思路：

因为在二维数组中，是按照从上到下递增，从左到右递增的，那么每一行每一列的最右上角的数，肯定是这一行最大的数，这一列最小的数，那么就有这三种情况：
1.当右上角的数比查找数小时：右上角的数是当前这一行最大的数，那么就应该row++
2.当右上角的数比查找数大时：右上角的数是当前这一列最小的数，那么就应该col–
3.当右上角的数等于查找数时：找到所查找的数，over

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
public class Solution {
    public boolean Find(int target, int [][] array) {
    	boolean flag = false;
        int rows = array.length;
        if(rows > 0){
        	int cols = array[0].length;
            int row = 0;
            int col = cols - 1;
            while(row < rows && col >= 0){
            	if(array[row][col] == target){
                	flag = true;
                    break;
                }
                if(array[row][col] > target){
                	col--;
                }else if(array[row][col] < target){
                	row++;
                }
            }
        }
        
        return flag;
    }
}