My code:
public class Solution {
public boolean searchMatrix(int[][] matrix, int target) {
if (matrix == null || matrix[0].length == 0 || matrix.length == 0)
return false;
int[] oneD = new int[matrix.length * matrix[0].length];
for (int i = 0; i < oneD.length; i++)
oneD[i] = matrix[i / matrix[0].length][i % matrix[0].length];
int lo = 0;
int hi = oneD.length - 1;
return BinarySearch(lo, hi, target, oneD);
}
private boolean BinarySearch(int lo, int hi, int target, int[] oneD) {
if (lo > hi)
return false;
int mid = (lo + hi) / 2;
if (oneD[mid] > target)
return BinarySearch(lo, mid - 1, target, oneD);
else if (oneD[mid] < target)
return BinarySearch(mid + 1, hi, target, oneD);
else
return true;
}
}
My test result:
这道题目我就偷懒了，直接把二维数组转换为一维数组，然后二分查找找出来。
如果一定要用二维，也不难，只是需要涉及到一维坐标而二维坐标的一个转换，懒得烦了。
第七十题，mark。
来分享一个今天遇到的事。
来美国第四天， 第一次碰到歧视。我是真的没想到，在这么一个无比偏僻偏僻的比地方，都他妈有人歧视中国人。
我去超市找鸡蛋，没找着。去问一个女服务员，她说，在最后面。
于是我去最后面找，没找到。然后正好又有个工作人员，于是我问他，
excuse me, where are eggs?
然后他说他没听懂，我当时真信了。于是尝试着用几种不同的语调重复eggs来问他。
他说他还是听不懂。我以为美国人不把鸡蛋叫eggs？否则这么简单的单词，我发音再怎么不标准，也不会听不懂啊。
于是我拿出手机查电子词典，这是正好又走过来一个工作人员，他就和这个人聊起来，一边聊一边看我一眼。发现我还在边上。我查到了单词，发现就是eggs，就想等他们聊完，再问他。结果他聊一会儿看我一会儿，然后就不停的聊下去。我在那里也很尴尬，我以为他们都是友好的，毕竟刚到这个国家的时候，这里的人给我的印象很不错。结果他们就是不停。
我已经感受出一点什么了。于是自己去找了，最后找到了。
回到了宿舍，我去和房管聊了下。我问她，你们美国人怎么叫鸡蛋的？她说，eggs
我就说，我在超市问他们鸡蛋在哪里，他们怎么听不懂。
房管表示不能理解，因为她觉得我的发音是正确的。
结合着，那家伙后来一直聊天，故意不让我有问他的机会，我明白了。
之前也在晓松奇谈里面看到过，美国如果在公共场合说出反种族言论是犯法的，所以，他只能这么做来表示对我的歧视。
何必呢？真的有那么大的不满吗？
真的，在哪里都有傻逼啊。
摆正心态吧。
**
总结：binary search
**
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;
if (matrix[matrix.length - 1][matrix[0].length - 1] < target)
return false;
int begin = 0;
int end = matrix.length * matrix[0].length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
int row = middle / matrix[0].length;
int col = middle % matrix[0].length;
if (matrix[row][col] < target) {
begin = middle + 1;
}
else if (matrix[row][col] > target) {
end = middle - 1;
}
else {
return true;
}
}
return false;
}
}
第一次的做法太渣了。。。人神共怒！
第二次尽管依然是binary serach，并且把2-d当成1-d做，但是我没有申请额外内存。直接坐标转换就做出来了。
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 begin = 0;
int end = matrix.length - 1;
while (begin <= end) {
int middle = begin + (end - begin) / 2;
if (matrix[middle][0] > target) {
end = middle - 1;
}
else if (matrix[middle][0] < target) {
if (target <= matrix[middle][matrix[0].length - 1]) {
end = middle;
break;
}
else {
begin = middle + 1;
}
}
else {
return true;
}
}
if (end < 0)
return false;
int head = 0;
int tail = matrix[0].length - 1;
while (head <= tail) {
int middle = head + (tail - head) / 2;
if (matrix[end][middle] > target) {
tail = middle - 1;
}
else if (matrix[end][middle] < target) {
head = middle + 1;
}
else {
return true;
}
}
return false;
}
}
第二次的做法真的很棒！2D -> 1D来做，思路清晰，也没有很多的corner case
第三次我是先列 Binarysearch，确定好行，再去该行Bianry search
一个corner case 没考虑到。end 可能小于0，此时代码所要找的数，小于matrix最小值。
Anyway, Good luck, Richardo! -- 08/09/2016
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 row = matrix.length;
int col = matrix[0].length;
int begin = 0;
int end = row * col - 1;
while (begin <= end) {
int mid = begin + (end - begin) / 2;
int i = mid / col;
int j = mid % col;
if (matrix[i][j] > target) {
end = mid - 1;
}
else if (matrix[i][j] < target) {
begin = mid + 1;
}
else {
return true;
}
}
return false;
}
}
2D -> 1D
clear and simple
Anyway, Good luck, Richardo！ -- 09/21/2016
