題目描述

在一個(gè)二維數(shù)組中，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

?

思路
法一： * 矩陣是有序的，從左下角來看，向上數(shù)字遞減，向右數(shù)字遞增， * 因此從左下角開始查找，當(dāng)要查找數(shù)字比左下角數(shù)字大時(shí)。右移 * 要查找數(shù)字比左下角數(shù)字小時(shí)，上移
時(shí)間復(fù)雜度O(m+n)? 法二：
每行都用折半查找。時(shí)間復(fù)雜度是nlogn

AC代碼：

1 class Solution { 2 public: 3 bool Find(vector<vector<int> > array,int target) { 4 int i,j,m,n; 5 m=array.size();//行 6 n=array[0].size();//列 7 8 i=0,j=m-1; 9 10 while(i<n&&j>=0) 11 { 12 if(array[i][j]>target) 13 j--; 14 else if(array[i][j]<target) 15 i++; 16 else 17 return true; 18 } 19 return false; 20 } 21 };

?

轉(zhuǎn)載于:https://www.cnblogs.com/SeekHit/p/5755826.html

總結(jié)

以上是生活随笔為你收集整理的剑指Offer 二维数组中的查找的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。