题目链接

题目描述

在一个二维数组中（每个一维数组的长度相同）

  • 每一行都按照从左到右递增 的顺序排序，
  • 每一列都按照从上到下递增 的顺序排序。

请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

示例

现有矩阵 matrix 如下： 

  1. [
  2.   [1,   4,  7, 11, 15],
  3.   [2,   5,  8, 12, 19],
  4.   [3,   6,  9, 16, 22],
  5.   [10, 13, 14, 17, 24],
  6.   [18, 21, 23, 26, 30]
  7. ]
  • 给定 target = 5，返回 true。
  • 给定 target = 20，返回 false。

解题思路

二维数组是有规律的：右上角的数字是一列中最小的、一行中最大的，通过这个数字和 target 进行对比，可以将一行或者一列作为候选区域排出，那么 target 可能存在的范围缩小，最终得出结果。

代码

  1. public class Solution {
  2.     public boolean Find(int target, int [][] array) {
  3.         if(array.length==0){
  4.             return false;
  5.         }
  7.         //定义右上角坐标
  8.         int i=0,j=array[0].length-1;
  9.         for(;i<=array.length-1&&j>=0;){
  10.             if(array[i][j] > target){
  11.                 j--;
  12.             }else if(array[i][j] < target){
  13.                 i++;
  14.             }else{
  15.                 return true;
  16.             }
  17.         }
  18.         return false;
  19.     }
  20. }

代码分析

首先定义右上角坐标 ( i =0 , j = array[0].length-1 )
因为每一行的比较都需要从最大的地方开始
循环条件中，因为横坐标是一直往大变，即i++ , 纵坐标是一直往小变，即 j—
所以循环条件中， i <= array.length-1 && j >= 0