二维数组中的查找

题目描述

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

例如：在下面这个数组当中查找数字7，返回true;查找数字5返回false

【【1 2 8 9】

​ 【3 4 9 12】

​ 【4 7 10 13】

​ 【6 8 11 15】】

解题思路

• 首先可以想到的是直接遍历，但是想想如果直接遍历数组肯定浪费了从左到右，从上到下增大的条件所以排除
• 然后想到的是想到的是利用给定的条件进行相对应的排除，但是怎么样才能进行对应的排除呢？发现数组的右上角和数组的左下角成为了链接的重要部分。以右上角为例。首先将目标target和右上角的这个数array[i][j](其中i=0,j=array[0].length-1)进行比较就会有三种情况产生
  • target==array[i][j],直接返回true
  • target>array[i][j],因为array[i][j]是这一行最大的，所以这一行直接排除掉了,所以搜索剩下的行就行
  • target<array[i][j]，因为array[i][j]是这一列最小的，所以这一列直接排除掉了，所以搜索剩下的列就行

代码实现

java实现的

public class Solution {
    public boolean Find(int target, int [][] array) {
       if(array==null)
           return false;
        int n = array.length;
        int m = array[0].length;
        if(n==0||m==0)
        	return false;
        int i = 0;
        int j = m-1;
       //查看最右上角的位置
        while(i<n&&i>=0 && j<m && j>=0){
            if(target==array[i][j])
                return true;
            else if(target>array[i][j])//不要写成 if 结构
                i++;
            else if(target<array[i][j])
                j--;
        }
        return false;
    }
}

需要注意的点：

• 特殊输入测试：null值

• if else if不要写出if，因为当i++时，可能导致了i>=n

  下面再进行判断可能会造成越界，开始这个问题就导致我失败了，差之毫厘，谬以千里，需要注意

总结

这题是《剑指offer》上的面试题4，其实开始也不会写，看了答案才会，希望慢慢刷题后面会有进步，加油。