题解 | #二维数组中的查找#
二维数组中的查找
http://www.nowcoder.com/practice/abc3fe2ce8e146608e868a70efebf62e
线性查找：时间复杂度O(n+m),空间复杂度O（1）
思路：一、起点的选择：根据（1)向右递增 (2)向下递增的规律，可以选择（右上）和（左下）两个节点
二、why？
1、为什么选择（右上/左下）:
因为对于右上角节点来说，他有两个方向可以走，一个向左（递减），一个向下（递增），如果遇到目标值大于当前值的时候可以选择向下走，目标值小于当前值的时候可以向左走（左下角也是一样）
2、为什么不能选择其他起点：
但是如果选择左上角的节点的话，它的行走方向是向下(递增)，向右(递增)，如果遇到（左上角）大于等于目标值的时候确实好判断，如果是等于那就直接选当前这个指，如果大于那就是没结果
但是如果小于呢？是选择往下递增还是往右递增呢？
public class Solution {
public boolean Find(int target, int [][] array) {
int n = array.length;
int m = array[0].length;
int H = 0;
int L = m-1;
int temp;
//为什么要定义右上角呢，因为对于右上角来说，左边移动是减少，向下移动是增加（左下角也可以）
//如果选择左上角，那么往右移和往下移动都是递增，那应该如何选择呢？
while(H<n&&L>=0){
temp=array[H][L];
if(temp==target)return true;
else if(temp>target){
L--;
}
else{
H++;
}
}
return false;
}
}
查看10道真题和解析