劍指Offer題目1：二維數組中的查找

題目描述：　

　　http://ac.jobdu.com/problem.php?cid=1039&pid=0

　　在一個二維數組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。

　　請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。

輸入：

　　輸入可能包含多個測試樣例，對于每個測試案例，

　　輸入的第一行為兩個整數m和n(1<=m,n<=1000)：代表將要輸入的矩陣的行數和列數。

　　輸入的第二行包括一個整數t(1<=t<=1000000)：代表要查找的數字。

　　接下來的m行，每行有n個數，代表題目所給出的m行n列的矩陣(矩陣如題目描述所示，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。

輸出：

　　對應每個測試案例，

　　輸出”Yes”代表在二維數組中找到了數字t。

　　輸出”No”代表在二維數組中沒有找到數字t。

?

樣例輸入：　

3 3

5

1 2 3

4 5 6

7 8 9

3 3

1

2 3 4

5 6 7

8 9 10

3 3

12

2 3 4

5 6 7

8 9 10

樣例輸出：

Yes

No

No

?

題目解答分析

失敗解答1：用二維遍歷

　　這個題要是按普通的二維遍歷來查找的話，也能完成功能，但是就體現不出二維數組原先有序的優勢了。

　　如果數組非常大的話，會特別浪費時間。

　　但是我做的時候還是首先采取了這個二維遍歷的方法，因為我開始想的是，我需要讀入所有的數據，也只能一個一個讀，這已經是一個二維遍歷，那就只好在讀的時候順便進行查找了。

　　程序如下：

程序嘗試1：雙層循環 #include <iostream> using namespace std;int main(int argc, char* argv[]) {int row = 0, col = 0, t = 0;int testNum[100][100];bool isFound = false;while(cin >> row >> col >> t){isFound = false;for(int i = 0; i < row ; ++i){for(int j = 0; j < col; ++j){//輸入每個數cin>>testNum[i][j];//邊輸入邊驗證if(false == isFound && t == testNum[i][j]){ //已經找到后就沒必要再找了isFound = true;}}}if(true == isFound){cout << "Yes" << endl;}else{cout << "No" << endl;}}return 0; }

?

　　果然提交以后就顯示Time Limit Exceed了。

　　想必，未顯示的測試用例中必然有很大的二維數組。

?

進一步思考：利用數組有序特點

　　所以題目給的有序的條件是必須要用的，但是注意到這個有序也不是單純的有序，行與行之間也只是上面的元素比下面的元素小的關系，并不代表第二行的數一定大于第一行，比如第一行可以是1,2,3,4，而第二行可以是2,3,4,5。

　　先定位行再定位列的想法也不行，因為不論是第一列還是最后一列，都不足以作為本行的鍵值，因為各行之間的元素還是可能重疊的。而且，比如，目標值t有可能比第一列的所有元素都大，所以想根據第一個元素來查找是不行的。

?

書中的思路：

　　從數組中選取數字，和目標數字的關系有三種情況：=，<或>。

　　如果是等于則查找成功；

　　如果是數組中元素小于要查找的數字，說明要查找的數字應該在當前位置的右邊或下邊。

　　如果是數組中元素大于要查找的數字，說明要查找的數字應該在當前位置的左邊或上邊。

　　但是這兩個區域還有可能有重疊，比如右邊或下邊會在右下角有重疊。

　　解決方法：

　　如果查找從右上角開始，如果要查找的數字不在右上角，則每次可以剔除一列或一行。

　　也可以從左下角開始，但是不能從左上角或者右下角開始。　

?

別人的解答

　　http://www.cnblogs.com/remlostime/archive/2012/11/21/2780352.html

　　于是搜到了如上的解答。

　　可見這個查找是從矩陣的右上角開始進行的（本行最大，本列最小）；

　　如果查找成功，則返回；

　　如果查找失敗，矩陣元素值比t小則下移一行，矩陣元素值比t大則左移一列。

　　這樣把大小關系和調整的兩個方向就分開了，經過一些移動，如果查找成功則返回Yes，如果矩陣走完，則表明沒有找到。

　　這樣是可以實現（實現代碼附在后面），可以通過本文所列的測試用例，但是提交到九度上，還是超時了。

　　暫時沒有解決辦法，先休息吧，很晚了。。

?

題目解答代碼　

解答方法2 #include <iostream> using namespace std;int main(int argc, char* argv[]) {int row = 0, col = 0, t = 0;int testNum[1000][1000];bool isFound = false;while(cin >> row >> col >> t){//先將數組全部讀入for(int i = 0; i < row ; ++i){for(int j = 0; j < col; ++j){//輸入每個數cin>>testNum[i][j];}}//標志變量，記錄查找是否成功isFound = false;//然后進行查找for(int i = 0, j = col -1; false == isFound && i < row && j >= 0;){//找到之后循環就不必再進行if(testNum[i][j] == t){isFound = true;}else if(testNum[i][j] < t){++i;//換到下一行 }else{--j;//換到前一列 }}//最后輸出結果if(true == isFound){cout << "Yes" << endl;}else{cout << "No" << endl;}}return 0; }

?

?

工具推薦

　　一個測試程序很方便的工具，使用如圖：

?

　　首先設置好測試用例和標準輸出（即正確情況下的輸出），然后加入要運行的程序的exe文件（注意每次修改代碼都需要重新加一次），最后點擊運行即可查看結果。如果正確，會有對話框顯示AC。

　　附上網盤分享鏈接：

　　http://pan.baidu.com/share/link?shareid=518071&uk=2701745266

?　　在測試用例比較長的時候不用每次都重復輸入耽誤時間了。

?

參考資料：

　　《劍指Offer：名企面試官精講典型編程題》九度Online Judge收錄：

　　http://ac.jobdu.com/contest.php?cid=1039

　　何海濤的日志：

　　http://zhedahht.blog.163.com/blog/#m=0

　　解法：

　　http://www.cnblogs.com/remlostime/archive/2012/11/21/2780352.html

?

轉載于:https://www.cnblogs.com/mengdd/archive/2013/03/09/2951085.html

總結

以上是生活随笔為你收集整理的算法题001 剑指Offer 面试题三：二维数组中的查找的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。