My code:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0)
return false;
for (int i = 0; i < matrix.length; i++) {
int begin = 0;
int end = matrix[0].length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
if (matrix[i][middle] > target) {
end = middle - 1;
}
else if (matrix[i][middle] < target) {
begin = middle + 1;
}
else
return true;
}
}
return false;
}
}
我觉得这道题木就是每一行用一次binary seach，O(n log m), 没什么难的。
Anyway, Good luck, Richardo!
My code:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int i = 0;
int j = matrix[0].length - 1;
while (i < matrix.length && j >= 0) {
int curr = matrix[i][j];
if (curr == target) {
return true;
}
else if (curr > target) {
j--;
}
else {
i++;
}
}
return false;
}
}
reference:
https://discuss.leetcode.com/topic/20064/my-concise-o-m-n-java-solution/2
time complexity: O(m + n)
这个做法，并没有很好地利用 binary search
然后 binary search 通俗的做法是下面这个链接：
https://discuss.leetcode.com/topic/19540/ac-java-solution-with-divide-and-conquer-follow-the-hide-tags/2
复杂度是 O(row * log(col))
具体思路就是，先找到 <= target 的所有行
然后分别进行 binary search
然后看了下我以前的做法，直接对所有行进行 Binary search,
其实在时间复杂度上没有区别。
Anyway, Good luck, Richardo! -- 09/21/2016
