LeetCode74搜索二维矩阵

目录

• 题目


• 解
  
  
  
  • 方法一：暴力搜索
  
  
  • 方法二：缩小边界范围
  
  
  • 方法三：将一维坐标转换为二维坐标
  
  
  • 方法四：2次二分查找
  
  
  
  

题目

LeetCode74 搜索二维矩阵

提示：

• m == matrix.length


• n == matrix[i].length


• 1 <= m, n <= 100


• -104 <= matrix[i][j], target <= 104

解

方法一：暴力搜索

遍历查找，O(mn)。

简单，但不是期望考察的算法。

bool searchMatrix1(vector>& matrix, int target) {
bool res = false;
for (auto &row : matrix) {
for (auto e : row) {
if (e == target) res = true;
}
}
return res;
}


方法二：缩小边界范围

从右上角开始，逐渐缩小数据查找范围，O(m+n)。

记坐标(row, col)对应值为M(row, col)，有

当M(row, col)
当M(row, col) > target时，边界左移一列；

相等时，说明已成功找到

bool searchMatrix(vector>& matrix, int target) {
if (matrix.size() == 0) return false;
int row = 0, col = matrix[0].size() - 1;
while (row = 0) {
if (matrix[row][col] row++; // 下移一行
else if (matrix[row][col] > target)
col--; // 左移一列
else
return true;
}
return false;
}


方法三：将一维坐标转换为二维坐标

先将一维坐标转换为二维坐标，然后用二分查找，O(mn)。

设矩阵M为m x n二维矩阵，看成一维数组就是M[0..m * n - 1].

设二分法初始位置begin = 0, end = m*n - 1，则mid = (begin + end) / 2。

这样，可以用标准的二分法，在begin~end之间查找target。

bool searchMatrix(vector>& matrix, int target) {
if (matrix.empty() || matrix[0].empty()) return false;
int begin, end;
int n1 = matrix.size(), n2 = matrix[0].size();
begin = 0;
end = n1 * n2 - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
int x = matrix[mid / n2][mid % n2];
if (x == target) return true;
else if (x begin = mid + 1;
else
end = mid - 1;
}
return false;
}


方法四：2次二分查找

第一次，对矩阵第一列进行二分查找，找到最后一个不大于目标值的元素；

第二次，在第一次查到的所在行进行二分查，判断目标值是否存在。

注：upper_bound是在给定范围中，查找大于目标值的第一个元素。返回的是一个迭代器。

bool searchMatrix(vector>& matrix, int target) {
// row对应matrix的matrix[?][0]元素，是第一个大于target的行
auto row = std::upper_bound(matrix.begin(), matrix.end(), target, [](const int b, const vector& a){ // 传入比较子的参数：b 是要查找的目标元素(target)，a是martix中的元素(vector)
return b });

if (row == matrix.begin()) return false;
--row; // 此时，row对应matrix的行，是最后一个matrix[?][0]不大于target的行
return std::binary_search(row->begin(), row->end(), target);
}