算法刷题笔记 - 二维数组中的查找

二维数组中的查找

  • 来源 : LeetCode - 剑指 Offer 04. 二维数组中的查找
  • 难度 : 中等
  • 标签 : 二叉搜索树(BST), 二分查找(BS)

    题目描述

  • 在一个 n * m 的二维数组中,每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个高效的函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
  • 示例 :

  • 给定 target = 13,返回 true。

  • 给定 target = 20,返回 false。

    解法一:二叉搜索树

    解法构思:
  • 根据本题的二维表格具有的特点可以和二叉搜索树相类比,以右上角为轴逆时针旋转45度,将表格的右上角看作根,同行的小的相邻列为根的左孩子,同列的大的相邻行为有孩子,如下图所示。

  • 那么利用二叉搜索树的查找算法就可以解决此题

  • 以查找13为例,如下图,

    • 15为根,13小于15,查找左子树(根为11)
    • 11为根,13大于11,查找右子树(根为16)
    • 16为根,13小于16,查找左子树(根为9)
    • 9为根,13大于9,查找左子树(根为14)
    • 14为根,13小于14,查找左子树(根为13)
    • 查找成功
  • 类似于二叉树的,若查找失败,则一定终止于Nil区。比如,在根为13的树中查找12,如下图。

    • 13为根,12小于13,查找左子树(根为10)
    • 10为根,12大于10,查找右子树(根为18)
    • 18为根,12小于18,查找左子树(根为非法(Nil))
    • 查找失败,即不存在元素12

上手编程:

  • 将表抽象成树,定义left,right为根据根获得左右子树根的函数;isNull为判断根是否为空(Nil)
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    inline tuple<int, int> left(const tuple<int, int> & root) {
    return {get<0>(root), get<1>(root) - 1};
    }
    inline tuple<int, int> right(const tuple<int, int> & root) {
    return {get<0>(root) + 1, get<1>(root)};
    }
    class Solution {
    public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if (matrix.empty()) return false;
    if (matrix.front().empty()) return false;
    const int n = matrix.size();
    const int m = matrix.front().size();

    // Nil判断
    auto isNull = [n, m] (const tuple<int, int> & root) {
    const int r = get<0>(root);
    const int c = get<1>(root);
    return !((r >= 0 && r < n) && (c >= 0 && c < m));
    };

    // 获取传入根的值
    auto getValue = [&matrix] (const tuple<int, int> & root) {
    return matrix[get<0>(root)][get<1>(root)];
    };

    auto root = tuple<int, int>{0, m - 1};
    while (1) {
    const auto rootVal = getValue(root);

    // 判断是否匹配
    if (rootVal == target) return true;

    if (target < rootVal) root = left(root); // 查找左子树
    else root = right(root); // 查找右子树

    // 为空即为查找失败
    if (isNull(root)) return false;
    }
    }
    }
    • 直接按表来操作
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      class Solution {
      public:
      bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
      int i = matrix.size() - 1, j = 0;

      while(i >= 0 && j < matrix[0].size()) {
      if(matrix[i][j] > target) i--;
      else if(matrix[i][j] < target) j++;
      else return true;
      }
      return false;
      }
      }

      解法二:二分搜索,递归查找,减而治之

      解法构思:
    • 表的表示是有序的,很容易想到使用二分查找,但是二维表肯定不会像一位表一样简单,下面来分析。
    • 表是n行m列的。
    • (a, b)-> (c, d) 表示一个区域,区域的起点是a行b列, 终点是c行d列。
    • 查找的范围是一个矩形,如果我们先以二分查找第一行,那么,我们可以找到第一个大于等于目标值的数所在列C,
      • 相等直接返回。
      • 若是大于,我们这样想,第一行的C列都大于目标值,下面行更大,所以就将范围锁定在C列的左边的矩形区域。然后,在以二分查找C - 1列,找到一个大于等于目标值的行R
        • 相等直接返回。
        • 若是大于,我们这样想,C - 1列的R行都大于了目标值,R行下面的更大,所以就将搜索区域缩小到了R行及R行以下
  • 经过这样的查找,我们将区域从(1, 1)-> (n, m) 缩小到了(R, 1) -> (n, C - 1)
  • 在(R, 1) -> (n, C - 1) 里递归搜索目标值
  • 最终矩形区域会退化成3种情况(即递归基) :
    • 单行,二分查找后返回
    • 单列,二分查找后返回
    • 空,直接返回
      • 下图是查找13的过程:

上手编程:

  • 利用std::lower_bound可以二分查找,但是当搜索一列时,我们需要给定一个Comparator,因为没有可以访问一列的迭代器,我们使用 vector< vector< int > > 的迭代器来模拟。技术使用到了Lambda的bind用法,见文章C++ lambda表达式简介及作用
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    56
    57
    58
    59
    60
    // 第c列的比较器的生成器
    // 只能用于lower_bound, 因为lower_bound里只会像comp(*iter, val)调用,
    // 但是binary_search除此之外还会这样调用comp(val, *iter)
    auto g_2DRowComparatorCreator = [] (int c) {
    return [c] (const vector<int> & r1, int v) {
    return r1[c] < v;
    };
    };

    class Solution {
    public:
    bool findNumberIn2DArray(vector<vector<int>>& matrix, int target) {
    if (matrix.empty()) return false;
    if (matrix.front().empty()) return false;
    const int n = matrix.size();
    const int m = matrix.front().size();

    return findNumberIn2DArray(matrix, 0, n, 0, m, target);
    }
    bool findNumberIn2DArray(
    vector<vector<int>>& matrix, int startr, int endr, int startc, int endc, int target) {
    // Null
    if (startr == endr || startc == endc) return false;
    // one row
    if (startr + 1 == endr) {
    auto low = (matrix.begin() + startr)->begin() + startc;
    return binary_search(low, low + endc - startc, target);
    }
    // one col
    if (startc + 1 == endc) {
    auto low = matrix.begin() + startr;
    auto iter = lower_bound(
    low, low + endr - startr, target, g_2DRowComparatorCreator(startc));
    if (low + endr - startr != iter && (*iter)[startc] == target) return true;
    return false;
    }

    const auto col_begin = matrix.begin() + startr;
    const auto row_begin = (col_begin)->begin() + startc;

    // find in row-startr
    auto iter_findInRow = lower_bound(row_begin, row_begin + endc - startc, target);
    if (row_begin + endc - startc != iter_findInRow && *iter_findInRow == target)
    return true;
    if (iter_findInRow == row_begin) return false;
    endc = iter_findInRow - (row_begin - startc);

    // find in col
    auto iter_findInCol = lower_bound(
    col_begin, col_begin + endr - startr, target, g_2DRowComparatorCreator(endc - 1));
    if (col_begin + endr - startr != iter_findInCol &&
    (*iter_findInCol)[endc - 1] == target)
    return true;
    if (iter_findInCol == col_begin) return false;
    startr = iter_findInCol - (col_begin - startr);

    // 递归调用
    return findNumberIn2DArray(matrix, startr, endr, startc, endc, target);
    }
    };

    效率比较

    • 解法一的程序1
    • 解法一的程序2
    • 解法二
    • 单次测算,没有太多参考价值。但可以说明3种程序效率都不低,自己想出解法2甚至有可能略胜官方解法一筹。