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

2017/3/8 posted in  算法-数据结构  

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

解题思路

假设二维数组为N行,M列。则初始下标变量int i=0; int j = M-1;。此时选取a[i][j]作为比较标准:

  • 若target == a[i][j],则表明已找到对应的数字,返回true;
  • 若target > a[i][j],由于数组是从左至右递增的,所以这一行左边的数据都要比a[i][j]小,所以可以排除,此时将i++,作为新的比较标准;
  • 若target < a[i][j],由于数组是从上而下递增的,该列的所有数字都比target大,不需要比较,则将j--,作为新的比较标准;
  • 若遍历到i==n,j==0,依旧没有找到匹配数据,则返回false;

实现代码

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

    }
}