剑指Offer_1

发表于 | 分类于

题目

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

解题思路

在一个以A[0][0]为起点，往X和Y方向增长的二维数组中，找一个特定的target。
为了降低算法平均的复杂度，选取+45°角的对角线两个顶点的任一一个为起点，这个选取左下角。

当A[x][y] == target 返回true
当A[x][y] < target，++y扩大A[x][y]的值， 反之，缩小其值。

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) {
		if(array == null || array.length == 0 || array[0].length == 0){
            return false;
        }
        int row = array.length;
        int col = array[0].length;
        int x = --row;
        int y = 0;
        
        for( ; x >= 0 && y < col; ){
            if(array[x][y] == target){
                return true;
            }
            else if(array[x][y] < target){
                ++y;
            }
            else{
                --x;
            }
        }
        return false;
    }
}