LeetCode 74. 搜索二维矩阵
原题链接
中等
作者:
bruce
,
2021-01-26 17:07:40
,
所有人可见
,
阅读 205
/**
* 方法 1,可以使用二分查找的思路来做,用两个二分来确定范围
* 第一个二分来确定在哪一行,第二个二分判断在哪一个列
* 使用第一个二分确定行之后,要分情况讨论一下,
* 首先如果l是第一行的话直接确定,
* 如果l是其他行的话,判断上一行的最后一个数是不是大于等于t,如果大于的话,说明在l-1这一行
* 否则最后应该是在l行不用减一
* 确定行之后,在确定列,还是使用二分查找即可
*/
bool searchMatrix(vector<vector<int>> &mat, int t)
{
if (mat.empty() || mat[0].empty()) return false;
int row = mat.size(), col = mat[0].size();
int l = 0, r = row - 1;
// 先确定在哪一行
int k = 0;
if (row > 1)
{
while (l < r)
{
int mid = (l + r) >> 1;
if (mat[mid][0] >= t) r = mid;
else l = mid + 1;
}
if (mat[l][0] == t) return true;
// 行的三种情况
if (l == 0) k = 0;
else if (mat[l - 1][col - 1] >= t) k = l - 1;
else k = l;
}
l = 0, r = col - 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (mat[k][mid] >= t) r = mid;
else l = mid + 1;
}
if (mat[k][l] == t) return true;
return false;
}
/**
* 方法 2,整个二维数组是严格有序的,所以可以把二维数组转换为1位数组来组,注意映射空间关系
* mid -> [mid / col][mid % col]
* 然后按照一位二分来做即可
* */
bool searchMatrix3(vector<vector<int>> &mat, int t)
{
if (mat.empty() || mat[0].empty())
return false;
int row = mat.size(), col = mat[0].size();
int l = 0, r = row * col - 1;
while (l < r)
{
int mid = (l + r) >> 1;
if (mat[mid / col][mid % col] >= t) r = mid;
else l = mid + 1;
}
if (mat[l / col][l % col] == t) return true;
else return false;
}