NeetCode 150 - Search 2D Matrix を解いた
NeetCode 150 - Search 2D Matrix を解いた
Roadmap - NeetCode の 150 問を C++ で解き進めています。
2 ヶ月ぶりに NeetCode の問題を解きました。
- 進捗: 29 / 150
今回は、Binary Search(二分探索)の Search 2D Matrix を解きました。
My Answer
Time: O(M * N)
Binary Search の問題なのに、無視して解いてしまったw
Accepted にはなったが、Solution より遅い。
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
for (int i = 0; i < matrix.size(); i++) {
if (matrix[i][0] > target) {
return false;
} else if (matrix[i][matrix[i].size() - 1] >= target) {
for (int j = 0; j < matrix[i].size(); j++) {
if (matrix[i][j] == target) {
return true;
}
}
return false;
}
}
}
};
Solution
Time: O(log M + log N)
Binary Search で、該当の行 -> 該当の列の順で絞り込んで target が存在するか判別します。
- 該当の行を探す:
O(log M)- 1 つめの
while
- 1 つめの
- 該当の列を探す:
O(log N)- 2 つめの
while
- 2 つめの
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int ROWS = matrix.size();
int COLS = matrix[0].size();
int top = 0, bottom = ROWS - 1;
while (top <= bottom) {
int row = (top + bottom) / 2;
if (target > matrix[row][COLS - 1]) {
top += 1;
} else if (target < matrix[row][0]) {
bottom -= 1;
} else {
break;
}
}
if (top > bottom) {
return false;
}
int row = (top + bottom) / 2;
int l = 0, r = COLS - 1;
while (l <= r) {
int m = (l + r) / 2;
if (target > matrix[row][m]) {
l += 1;
} else if (target < matrix[row][m]) {
r -= 1;
} else {
return true;
}
}
return false;
}
};
