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:
這道題目我就偷懶了，直接把二維數(shù)組轉(zhuǎn)換為一維數(shù)組属愤，然后二分查找找出來愉适。
如果一定要用二維，也不難，只是需要涉及到一維坐標(biāo)而二維坐標(biāo)的一個轉(zhuǎn)換暑脆，懶得煩了渠啤。
第七十題，mark添吗。
來分享一個今天遇到的事沥曹。
來美國第四天， 第一次碰到歧視根资。我是真的沒想到架专，在這么一個無比偏僻偏僻的比地方同窘，都他媽有人歧視中國人玄帕。
我去超市找雞蛋，沒找著想邦。去問一個女服務(wù)員裤纹，她說，在最后面丧没。
于是我去最后面找鹰椒，沒找到。然后正好又有個工作人員呕童，于是我問他漆际，
excuse me, where are eggs?
然后他說他沒聽懂，我當(dāng)時真信了夺饲。于是嘗試著用幾種不同的語調(diào)重復(fù)eggs來問他奸汇。
他說他還是聽不懂。我以為美國人不把雞蛋叫eggs往声？否則這么簡單的單詞擂找，我發(fā)音再怎么不標(biāo)準(zhǔn)，也不會聽不懂啊浩销。
于是我拿出手機查電子詞典贯涎，這是正好又走過來一個工作人員，他就和這個人聊起來慢洋，一邊聊一邊看我一眼塘雳。發(fā)現(xiàn)我還在邊上。我查到了單詞普筹，發(fā)現(xiàn)就是eggs败明，就想等他們聊完，再問他斑芜。結(jié)果他聊一會兒看我一會兒肩刃，然后就不停的聊下去。我在那里也很尷尬，我以為他們都是友好的盈包，畢竟剛到這個國家的時候沸呐，這里的人給我的印象很不錯。結(jié)果他們就是不停呢燥。
我已經(jīng)感受出一點什么了崭添。于是自己去找了，最后找到了叛氨。
回到了宿舍呼渣，我去和房管聊了下。我問她寞埠，你們美國人怎么叫雞蛋的屁置？她說，eggs
我就說仁连，我在超市問他們雞蛋在哪里蓝角，他們怎么聽不懂。
房管表示不能理解饭冬，因為她覺得我的發(fā)音是正確的使鹅。
結(jié)合著，那家伙后來一直聊天昌抠，故意不讓我有問他的機會患朱，我明白了。
之前也在曉松奇談里面看到過炊苫，美國如果在公共場合說出反種族言論是犯法的裁厅，所以，他只能這么做來表示對我的歧視劝评。
何必呢姐直？真的有那么大的不滿嗎？
真的蒋畜，在哪里都有傻逼啊声畏。
擺正心態(tài)吧。
**
總結(jié)：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當(dāng)成1-d做，但是我沒有申請額外內(nèi)存才睹。直接坐標(biāo)轉(zhuǎn)換就做出來了徘跪。
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逗抑，此時代碼所要找的數(shù)，小于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
