HHot 100C++ 图解

74. 搜索二维矩阵

中等 二分查找 3 帧动画 在力扣上做

一句话套路矩阵拉平成 [0,mn) 做一维二分

题目描述

给你一个满足下述两条属性的 m x n 整数矩阵:

  • 每行中的整数从左到右按非严格递增顺序排列。
  • 每行的第一个整数大于前一行的最后一个整数。

给你一个整数 target ,如果 target 在矩阵中,返回 true ;否则,返回 false 。

你必须编写一个时间复杂度为 O(log(m * n)) 的解决方案。

 

示例 1:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 3
输出:true

示例 2:

输入:matrix = [[1,3,5,7],[10,11,16,20],[23,30,34,60]], target = 13
输出:false

 

提示:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 100
  • -104 <= matrix[i][j], target <= 104

思路

时间O(log(mn))
空间O(1)

前提(与 Q240 的区别)

每行递增,且「下一行首元素 > 上一行末元素」,所以整块矩阵拉平后是一个有序数组 -> 直接在 [0, m*n) 上二分,不用写二维逻辑。

映射

mid -> matrix[mid / n][mid % n]

图解

j0 j1 j2 j3 i0 1 3 5 7 i1 10 11 16 20 i2 23 30 34 60
矩阵(来自本仓库测试数据,红色格子 = 0)

逐帧动画

1 / 3

快捷键:← → 单步,空格播放 / 暂停。

C++17 题解

src/11_binary_search.cpp21 行
namespace lc0074 {
class Solution {
 public:
  bool searchMatrix(vector<vector<int>>& matrix, int target) {
    if (matrix.empty() || matrix[0].empty()) return false;  // 防 matrix[0] 越界
    const int R = (int)matrix.size(), C = (int)matrix[0].size();
    int lo = 0, hi = R * C - 1;
    while (lo <= hi) {
      int mid = lo + (hi - lo) / 2;
      int v = matrix[mid / C][mid % C];
      if (v == target)
        return true;
      else if (v < target)
        lo = mid + 1;
      else
        hi = mid - 1;
    }
    return false;
  }
};
}

单元测试

以下用例都在本仓库里实际编译运行过,图解里的数据也取自这里。

TEST q74_search_a_2d_matrix11 行
lc0074::Solution s;
vector<vector<int>> m{{1, 3, 5, 7}, {10, 11, 16, 20}, {23, 30, 34, 60}};
CHECK_TRUE(s.searchMatrix(m, 3));
CHECK_FALSE(s.searchMatrix(m, 13));
CHECK_TRUE(s.searchMatrix(m, 1));    // 第一个元素
CHECK_TRUE(s.searchMatrix(m, 60));   // 最后一个元素
vector<vector<int>> one{{5}};
CHECK_TRUE(s.searchMatrix(one, 5));
CHECK_FALSE(s.searchMatrix(one, 4));
vector<vector<int>> none{};  // 空矩阵:不守卫就是 matrix[0] 越界
CHECK_FALSE(s.searchMatrix(none, 1));

↑↓ 选择↵ 打开/ 随时唤起