题目描述

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

输入
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的位置，但是可以排除行或列。