解決算法問題的一般方法 - 算法數據結構面試分享（一）

 先看一道題目： 給你一個整型數組，我想找出來最大的兩個數，能幫我寫一個算法嗎？

    拿到這個題目，大家會怎么想到用什么方法解決嗎？我見過很多同學的回答是，先排序，取最大的兩個數就好了。那么接下來我們的問題就變成了如何給這個整型數組排序了。我們有很多種方法，冒泡排序，快速排序等等。很有可能面試官就讓你開始寫具體的排序算法了。當然，有些有經驗的同學可能會說了，排序我直接調用sort方法就好了哈。

    其實，這兩種情況都沒有對錯之分，只是沒有敲開面試官的心扉，也沒有給人眼前一亮，讓自己脫穎而出。

    再看這道題，如果我是面試官，首先我想知道你對這道題的理解是什么？你打算怎么解決？你有什么問題要和我溝通確認的嗎？如果這些功課都到位了，就算代碼有些缺陷，面試官或許也不會計較，誰能無過哈。何況我們還是學生呢，經驗少點，但是我有潛力呀。

    好了，如果要問，我能問什么呢？

大家都知道溝通很重要，沒有哪一個項目是可以一個人去完成的。我列一些問題給大家參考哈：

1. 整型數組，數組的長度有限制嗎？（沒有提出來，基本上沒有限制）

2. 這個數組里數字的范圍已知嗎？（沒有提出來，基本上沒有特定范圍）

3. 找最大的數，那我能排序嗎？能調用已有的SDK嗎？（廢話，當然不行，要不怎么叫寫個算法呢）

4. 能改變原來的數組順序嗎？（如果排序，基本上是改變了，除非你又copy了一個數組）

5. 對算法的時間復雜度和空間復雜度有要求嗎？（當然越小越好）

6. 找最大的兩個數，如果數組里只有一個或者沒有數字怎么辦？（你覺得呢？有一個返回一個，另一個返回什么呢？ 0 還是 int.min 值，還是空值？哪一個更合理）

7. 如果數組是空怎么辦？（返回異常嗎？返回最小值嗎？返回空數組嗎？數組里返回空值嗎？）

8. 返回兩個數，用數組返回嗎？還是用參數返回？（那我們返回數據吧）

9. 返回兩個數，最大的放第一個，第二大的放第二個嗎？（假設是這樣吧）

10. 返回兩個數，這個需求會經常變更嗎？（返回3個？任意個？）

    我相信，可能你還能想到更多的問題。好了，我們能夠想象，就這些問題我們估計會討論個幾分鐘，當然，也會有面試官把問題踢回給你，讓你自己給答案，不合理的時候他可能還會問為什么。那我們就只能按照自己的理解把最佳方案寫出來了。這篇blog是為了拿這道題為例，總結解決算法和數據結構的一般方法，接下來的章節里我們會帶大家一起解析這道題。

    直接上干貨了哈。解決算法和數據結構問題一般會遵循以下6個步驟，而真正代碼其實其中的一兩步。

1. 確保你理解了問題，并且嘗試一個例子，確認理解無誤

2. 想想你可以用什么方法解決問題，你會選擇哪一種，為什么？

3. 解釋你的算法和實現的方法

4. 寫代碼的時候，記住，一定要解釋你現在在干什么

5. 拿一個實例，Work Through你的代碼

6. 修復缺陷，保證異常情況都被考慮到

   
   

當然，這中間如果你發現了新的問題，我們需要及時提出來。當我們寫不下去的時候，我們要再回到之前的例子中去，是不是我們的理解不對，當然面試官在這時候也會忍不住和你溝通的，除非你自己放棄了這個機會。

接下來的章節里，我們就按照這6部曲解析常見的算法和數據結構的問題了。

好了，歡迎大家關注我的公眾號，還有我的系列視頻教程,

• 數據結構與算法

• BAT、微軟經典算法面試題輔導

• 排序算法專題

• 鏈表算法的專題課程

大家有什么更好的解法，也歡迎討論哈。