剑指offer二刷 (1)二维数组中的查找

二维数组的查找

题目描述

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

思路：leetcode上面见过这道题。首先利用该排序矩阵的规律，我们发现通过右上角的数可以每一次淘汰掉一行或者一列数，因为右上角的数大于它所在行的所有数，并且小于它所在列的所有数。如果我们的目标结果大于右上角的数，就淘汰掉右上角这个数所在的一整行，往下找，反之如果目标结果小于右上角的数，则淘汰掉右上角的数所在的列，因为该列所有数都大于目标结果，以这个思路依次迭代，直到找到矩阵的边界，找到了就返回true, 否则返回false.

下面是递归版本的代码：

public class Solution {
   public  boolean Find(int target, int [][] array) {
       int row = array.length;
       int column = array[0].length;
       if (array == null || row == 0) {
           return false;
       }
       return helper(target, array, 0, column-1);
   }  
   public boolean helper(int target, int[][] array ,int i, int j) {
       if (array == null || i >= array.length || j < 0) {
           return false;
       }
       if (target > array[i][j]) {
           i++;
           return helper(target, array, i, j);
       } else if (target < array[i][j]) {
           j--;
           return helper(target, array, i, j);
       } else {
           return true;
       }
   }
}

下面是循环版本：

public class Solution {
   public  boolean Find(int target, int [][] array) {
       if (array == null || array.length < 1 || array[0].length < 1) {
           return false;
       }
       int row = 0;
       int column = array[0].length - 1;
       
       while (row < array.length && column >= 0) {
           if (target == array[row][column]) {
               return true;
           } else if (target > array[row][column]) {
               row++;
           } else {
               column--;
           }
       }
       return false;
   }
}