数据结构与算法

二维数组中的查找

略

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

分析

  例如这样的一个数组，若要查找数字7，则返回true；若要查找数字5，由于数组中不含有该数字,则会返回false。

1 2 8 9
2 4 9 12
4 7 10 13
6 8 11 15

​  我开始的思维是从左上角[0][0]开始查找，如果相等则返回true，如果要查找的数大于[0][0]位置的数则会出现：那个数可能出现在[0][0]左边和右边还有所有左右重叠的部分的这种情况。这样看来问题就复杂了，所以我思考了下，决定用另外的一种方法来实现查找。

​  我的思考是这样的，由于数字比较有三种情况：大于、小于、等于。等于就不用说了，直接返回true即可，对于大于和小于，我是否可以让它和移动对应起来，例如大于则向左移动，小于则向下移动，移动的出发点就可以设置在右上方，事实证明是可行的。例如要查找7：9大于7，则9下面的都大于9，也一定都大于7了，所以向左移动；8大于7，同理向左移动；2小于7，则2下面都比2大，可能会出现7，所以向下移动；4小于7，同理向下移动，7等于7，最后找到了数字返回true。例如要查找5，查找路径会是9→8→2→4→7→4→6，到达了[4][0]依然没有5，则返回false。

​  这样移动方向和比较大小就对应了起来，可以实现查找的功能了。

代码实现

代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Solution {
    public boolean Find(int target, int [][] array) {
        if(array == null||array.length<1||array[0].length<1){
            return false;//数组为空或左（右）宽度小于1，则返回false；
        }
      	//得到总长宽；
        int rows = array.length;
        int cols = array[0].length;
      	//要查找的位置；
        int row = 0;		//行
        int col = cols - 1;	//列
        while( row>=0 && row<rows && col>=0 && col<cols){//在范围内移动位置；
            if(array[row][col] == target){//相等则返回true；
                return true;
            }else if(array[row][col]>target){//大于则向左移动，小于则向下移动；
                col--;
            }else{
                row++;
            }
        }
        return false;//没找到返回false；
    }
}

总结

  1. 思考问题要全面，例如代码中必须要判断数组为空，或者不是个二维数组。
  2. 当问题复杂化了后，需要另辟蹊径。