题目描述

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

示例

  1. Consider the following matrix:
  2. [
  3.   [1,   4,  7, 11, 15],
  4.   [2,   5,  8, 12, 19],
  5.   [3,   6,  9, 16, 22],
  6.   [10, 13, 14, 17, 24],
  7.   [18, 21, 23, 26, 30]
  8. ]
  10. Given target = 5, return true.
  11. Given target = 20, return false.Copy to clipboardErrorCopied

思路

该二维数组中的一个数，小于它的数一定在其左边，大于它的数一定在其下边。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间，当前元素的查找区间为左下角的所有元素。

  • 右上查找

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

  • 左下查找

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