JZ4二维数组中的查找

描述

在一个二维数组array中（每个一维数组的长度相同）              ，每一行都按照从左到右递增的顺序排序 
  
 
  
 
  
 
  
 
  
 
  
 
  
，每一列都按照从上到下递增的顺序排序              。请完成一个函数













，输入这样的一个二维数组和一个整数 
  
  
  
  
  
  
 ，判断数组中是否含有该整数 
  
 
  
 
  
 
  
 
  
 
  
 
  
。 [[1,2,8,9], [2,4,9,12], [4,7,10,13], [6,8,11,15]] 给定 target = 7 
  
  
  
  
  
  
 ，返回 true













。 给定 target = 3

 


 


 


 


 


 


 
，返回 false 
  
  
  
  
  
  
 。 进阶：空间复杂度 O(1)O(1)  
 
 
 
 
 
 
，时间复杂度 O(n+m)O(n+m)

思路

利用该二维数组的性质： 每一行都按照从左到右递增的顺序排序 
   
   
   
   
   
   
  ， 每一列都按照从上到下递增的顺序排序 改变个说法
 

 

 

 

 

 

 
，即对于左下角的值 m
 

 

 

 

 

 

 
，m 是该行最小的数              ，是该列最大的数 每次将 m 和目标值 target 比较： 当 m < target 

 
 

 
 

 
 

 
 

 
 

 
 

 
，由于 m 已经是该行最大的元素













，想要更大只有从列考虑                     ，取值右移一位 当 m > target 
 
 
 
 
 
 
 
 
 
 
 
 
 
，由于 m 已经是该列最小的元素




















，想要更小只有从行考虑              ，取值上移一位 当 m = target 
  
 
  
 
  
 
  
 
  
 
  
 
  
，找到该值













，返回 true 用某行最小或某列最大与 target 比较 
  
  
  
  
  
  
 ，每次可剔除一整行或一整列

代码

package mid.JZ4二维数组中的查找; public class Solution { public boolean Find(int target, int [][] array) { //先判断特殊情况 if (array.length == 0) return false; int n = array.length; if (array[0].length == 0) return false; int m = array[0].length; //从上下最大 
  
  
  
  
  
  
 ，左右最小开始遍历 for (int i = n -1, j = 0; i >= 0 && j < m;) { //如果大了 if (array[i][j] > target) { //往上走 i--; } else if(array[i][j] < target) { //小了 往右走 j++; } else { //如果等于

 


 


 


 


 


 


 
，返回true return true; } } return false; } }