剑指Offer——二维数组中的查找

题目描述

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

输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true

题解

• 暴力法：遍历数组，O(n^m)
• 二分法：将每行或每列当做n或m个递增数组，分别进行二分查找。O(n*logm)

  public class Solution {
    public boolean Find(int target, int [][] array) {
        for(int row=0;row<array.length;++row){
            int left=0;
            int right=array[row].length-1;
            while(left<=right){
                int mid=(left+right)/2;
                if(array[row][mid]>target){
                    right=mid-1;
                }else if(array[row][mid]<target){
                    left=mid+1;
                }else{
                    return true;
                }
            }
        }
        return false;
    }
  }

• 二分变形法
  • 一维递增数组二分：基准小看右边，基准大看左边。
    • 基准：左、右、中间、随机。
  • 二维递增数组二分
    • 基准：左上角（下大、右大，无法确定方向，放弃）、左下角（上小、右大，可以排除当前列或行，可以）、右上角（左小、下大，可以排除当前列，可以）、右下角（上小、左小，无法确定方向，放弃）、中间（左上小，右下大，每次能排除1/4，但是较复杂）

以右上角为例：
- target小，则当前列排除
- target大，则当前行排除

public class Solution {
    public boolean Find(int target, int [][] array) {
        int row=0;
        int cell=array[0].length-1;
        while(row<array.length&&cell>=0){
            if(target==array[row][cell]){
                return true;
            }
            if(target<array[row][cell]){
                cell--;
            }else{
                row++;
            }
        }
        return false;
    }
}

启发

• 解题是第一位：最暴力的方法也是最直接的方法。
• 利用题目的特点：本题的特点是向右、向下递增+查找。由递增+查找可以引出“二分查找”，二分查找通常针对的是一维数组，因此直觉是进行多次二分查找。
• 多次二分查找只用到了一个方向的递增特点。因此可以假设还有更优方法。这时可以寻求互斥的特点：本题互斥的特点就是大与小、上与下、左与右。因为是二维数组，所以需要同时兼顾水平和垂直两个方向，因此可以结合上与右、下与左。从而可以从左下角或右上角分析：行或列要么大、要么小，夹角不确定，看似还是无法确定target的位置，但是可以排除行或列。