前言
眾所周知，對于面試而言渔欢，《劍指offer》是一本“好書”墓塌。
如果你和我一樣是個(gè)算法菜雞，那么最推薦的是先把劍指offer的題目搞明白奥额，其次再去刷LeetCode等習(xí)題苫幢，這樣對于面試突擊非常有用，因?yàn)槊嬖嚬僮畛垫挨？嫉乃惴}都在這本書里韩肝。
如果你發(fā)現(xiàn)看這本書很吃力，可以先直接參考些網(wǎng)上的代碼九榔，照著抄一遍哀峻，理解下算法題是應(yīng)該解題，多抄幾道題目哲泊，你就對算法題的做法有感覺了剩蟀，這個(gè)高考做固定套路數(shù)學(xué)題是一樣的。
對于劍指offer題解這個(gè)系列切威，我的寫作思路是育特，對于看過文章的讀者，能夠做到：
- 迅速了解該題常見解答思路（奇技淫巧不包括在內(nèi)牢屋，節(jié)省大家時(shí)間且预，實(shí)在有研究需求的人可以查閱其它資料）
- 思路盡量貼近原書（例如書中提到的面試官經(jīng)常會(huì)要求不改變原數(shù)組，或者有空間限制等烙无，盡量體現(xiàn)在代碼中锋谐，保證讀者可以不漏掉書中細(xì)節(jié)）
- 盡量精簡話語，避免冗長解釋
- 給出代碼可運(yùn)行截酷，注釋齊全涮拗，關(guān)注細(xì)節(jié)問題
- 代碼能夠通過牛客網(wǎng)在線編程《劍指offer》測試
《劍指offer題解》系列
你可以通過以下幾種途徑查看我的《劍指offer題解》系列：
- 關(guān)注我的公眾號：后端技術(shù)漫談迂苛，點(diǎn)擊公眾號導(dǎo)航欄：劍指offer題解
- 劍指offer題解專欄(CSDN)
- 各大博客平臺我的賬號（見本文最下方）
題目介紹
在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長度相同）三热，每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序三幻。請完成一個(gè)函數(shù)就漾，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)念搬。
解題思路
方法一
首先能夠想到的肯定是一行一行或者一列一列遍歷抑堡，判斷數(shù)組中是否含有該整數(shù)摆出。該方法顯然是最笨拙的二維數(shù)組遍歷，面試官也不會(huì)滿意首妖，時(shí)間復(fù)雜度是O(n^2)
代碼
Python
class Solution:
def Find(self, target, array):
for i in range(len(array)):
for j in range(len(array[0])):
if array[i][j]==target:
return True
return False
方法二
我們思考下偎漫，既然大的數(shù)字都在靠右邊/下邊，能否能利用行列的數(shù)據(jù)變化規(guī)律來優(yōu)化下解法有缆，如果尋找的目標(biāo)數(shù)大于現(xiàn)在的數(shù)字象踊，那么目標(biāo)數(shù)字是在當(dāng)前位置的右邊或下邊，如果所尋找的目標(biāo)數(shù)小于現(xiàn)在的數(shù)字棚壁，那么目標(biāo)數(shù)字在當(dāng)前位置的左邊或上邊杯矩。舉個(gè)例子，如下圖數(shù)組所示：
1 2 3 4
2 3 8 9
3 4 9 10
4 5 10 11
我們的位置是1袖外，要找8菊碟，8大于1，那么在1的右邊和下邊區(qū)域進(jìn)行下一步的搜索在刺。
如果我們先搜索他的右邊，
2 3 4
3 8 9
4 9 10
5 10 11
又搜索了他們的下邊头镊，
2 3 8 9
3 4 9 10
4 5 10 11
這時(shí)候我們發(fā)現(xiàn)
3 8 9
4 9 10
5 10 11
這個(gè)區(qū)域搜索了兩次蚣驼，我們是從數(shù)組的第一個(gè)數(shù)[0][0]取的，遇到了重復(fù)搜索區(qū)域的問題相艇。有沒有方法去除重復(fù)的搜索區(qū)域呢颖杏，我們發(fā)現(xiàn)，當(dāng)從右上角取第一個(gè)數(shù)的時(shí)候坛芽，可以去除重復(fù)的搜索區(qū)域，還是以這個(gè)數(shù)組為例，取4店煞，搜索8申鱼，發(fā)現(xiàn)8比4大，那么8不可能出現(xiàn)在4這一行活喊，只需要從下邊搜索即可丐膝。如果尋找3，3比4小钾菊，4那一列后續(xù)的數(shù)都大于4帅矗，只需要從左邊搜索即可。
1 2 3 4
2 3 8 9
3 4 9 10
4 5 10 11
我們還可以發(fā)現(xiàn)左下角的點(diǎn)也可以去除重復(fù)搜索區(qū)域煞烫，總結(jié)起來的話浑此，有點(diǎn)像變量控制法的感覺，將一個(gè)變量控制住滞详，根據(jù)另外一個(gè)變量的規(guī)律凛俱，得出結(jié)論紊馏。
這樣我們將時(shí)間復(fù)雜度降為了O(n)
代碼
Java
public class Solution {
public boolean Find(int target, int [][] array) {
int rows = array.length;
int cols = array[0].length;
int i = rows-1, j = 0;
while(i >= 0 && j < cols){
if(target < array[i][j])
i--;
else if(target > array[i][j])
j++;
else
return true;
}
return false;
}
}
Python
class Solution:
def Find(self, target, array):
if array == ([] or [[]]):
return False
row = len(array)
col = len(array[0])
i=0
j=col-1
while 0<=i<row and 0<=j<col:
if target>array[i][j]:
i=i+1
elif target<array[i][j]:
j=j-1
else:
return True
return False
總結(jié)
題目簡單，小伙伴們需要理解的是算法題應(yīng)該注重的是效率優(yōu)化最冰，暴力窮舉能夠解決問題瘦棋，但說服不了面試官。
我的《劍指offer題解》系列
你可以通過以下兩種途徑查看《劍指offer題解》系列：
- 關(guān)注我的公眾號：后端技術(shù)漫談暖哨，點(diǎn)擊公眾號下方：劍指offer題解
- 劍指offer題解專欄(CSDN導(dǎo)航頁)
- 各平臺博客
關(guān)注我
我是一名后端開發(fā)工程師赌朋。
主要關(guān)注后端開發(fā)，數(shù)據(jù)安全篇裁，爬蟲沛慢，物聯(lián)網(wǎng)，邊緣計(jì)算等方向达布，歡迎交流团甲。
各大平臺都可以找到我
- 微信公眾號：后端技術(shù)漫談
- Github：@qqxx6661
- CSDN：@Rude3Knife
- 知乎：@Zhendong
- 簡書：@蠻三刀把刀
- 掘金：@蠻三刀把刀
- 頭條：@后端技術(shù)漫談
原創(chuàng)博客主要內(nèi)容
- Java知識點(diǎn)復(fù)習(xí)全手冊
- Leetcode算法題解析
- 劍指offer算法題解析
- SpringBoot菜鳥入門實(shí)戰(zhàn)系列
- SpringCloud菜鳥入門實(shí)戰(zhàn)系列
- 爬蟲相關(guān)技術(shù)文章
- 后端開發(fā)相關(guān)技術(shù)文章
- 逸聞趣事/好書分享/個(gè)人興趣
個(gè)人公眾號：后端技術(shù)漫談
如果文章對你有幫助，不妨收藏黍聂，投幣躺苦，轉(zhuǎn)發(fā)，在看起來~
