leetcode_240 搜索二维矩阵 II

1. 题意

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

2. 题解

这个题目和搜索二维矩阵相似。

唯一不同是，

这个题目不保证前一行的末尾元素小于当前行的开头元素了。

因此不能压成一个一维数组进行处理了。

2.1 逐行、列二分

直接逐行、列二分。

逐列二分，时间复杂度$O(n\log m)$

class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int R = matrix.size(); int C = matrix[0].size(); for (int i = 0; i < C; ++i) { int l = 0; int r = R - 1; while ( l <= r ) { int mid = ((r - l) >> 1) + l; int v = matrix[mid][i]; if ( v == target )  return true; if ( v < target )  l = mid + 1; else  r = mid - 1; } } return false; }};

逐行二分，时间复杂度$O(m\log n)$

class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int R = matrix.size(); int C = matrix[0].size(); for (int i = 0; i < R; ++i) { int l = 0; int r = C; while ( l < r ) { int mid = ((r - l) >> 1) + l; int v = matrix[i][mid]; if ( v == target )  return true; if ( v > target )  r = mid; else  l = mid + 1; } } return false; }};

其实我们还可以小小的优化下：

对于最大元素（最右边）小于target的行，我们可以直接舍弃掉。

同样对于最小元素（最左边）大于target的行，我们可以直接舍弃掉。

由于任一列都是有序的，

因此可以二分查找第一个末尾元素不大于target的行ub；

同样可以二分查找第一个首元素大于target的行bb。

再在[ub,bb)所在范围的这些行进行行二分。

class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int n = matrix.size(); int R = n; int C = matrix[0].size(); int l; int r; l = 0; r = R; while ( l < r) { int mid = ((r - l) >> 1) + l; int v = matrix[mid][C - 1]; if ( v == target) return true; if ( v > target) r = mid; else l = mid + 1; } int ub = r; l = ub; r = R; while ( l < r) { int mid = ((r - l) >> 1) + l; int v = matrix[mid][0]; if ( v == target) return true; if ( v > target) r = mid; else l = mid + 1; } int bb = r; for (int i = ub;i < bb; ++i) { auto it = lower_bound(matrix[i].begin(), matrix[i].end(), target); if (it != matrix[i].end() && *it == target) return true; } return false; }};

2.2 二叉搜索树

同搜索二维矩阵一样，可以将矩阵看成以右上角为根的二叉搜索树。

图也用上个题目的图吧。

时间复杂度$O(n+m)$

class Solution {public: bool searchMatrix(vector<vector<int>>& matrix, int target) { if (matrix.empty()) return false; int n = matrix.size(); int R = n; int C = matrix[0].size(); int x = 0; int y = C - 1; while ( x < R && y >= 0) { int v = matrix[x][y]; if ( v == target) return true; if ( v > target) --y; else  ++x; } return false; }};

参考

三叶