a***e
发帖数: 413 | 1 题目
https://oj.leetcode.com/problems/search-a-2d-matrix/
我写的如下，先搜索行，再列。后面那个简短的是看到的别人的答案，简洁很多，但要
不要考虑行数*列数overflow的情况呢？多谢！
bool searchMatrix(vector > &matrix, int target) {
int row = matrix.size();
if (row==0) return false;
int col = matrix[0].size();
if (col==0) return false;
int rmin=0, rmax=row-1, cmin=0, cmax=col-1,rmid,cmid;
while (rmin<=rmax)
{
rmid = rmin+(rmax-rmin)/2;
if (matrix[rmid][0]>target)
{
rmax=rmid-1;
}
else if (matrix[rmid][cmax]
{
rmin=rmid+1;
}
else
{
while(cmin<=cmax)
{
cmid=cmin+(cmax-cmin)/2;
if (matrix[rmid][cmid]>target)
{
cmax=cmid-1;
}
else if (matrix[rmid][cmid]
{
cmin=cmid+1;
}
else
return true;
}
}
}
return false;
}
class Solution {
public:
bool searchMatrix(const vector>& matrix, int target) {
if (matrix.empty()) return false;
const size_t m = matrix.size();
const size_t n = matrix.front().size();
int first = 0;
int last = m * n;
while (first < last) {
int mid = first + (last - first) / 2;
int value = matrix[mid / n][mid % n];
if (value == target)
return true;
else if (value < target)
first = mid + 1;
else
last = mid;
}
return false;
}
}; |
|
