在前面課時中，我們學習了數據結構和算法思維，這些知識和技巧，是解決問題、代碼優化的基礎。從本課時開始，我們將進入實戰模塊，從真正解決問題的角度來看看，如何將我們此前學到的知識靈活運用到實際工作中。 #### 問題定位和技術選型 假設你現在面對一個實際的算法問題，則需要從以下兩個方面進行思考。 首先，我們要明確目標。即用盡可能低的時間復雜度和空間復雜度，解決問題并寫出代碼； 接著，我們要定位問題。目的是更高效地解決問題。這里定位問題包含很多內容。 例如： * 這個問題是什么類型（排序、查找、最優化）的問題； * 這個問題的復雜度下限是多少，即最低的時間復雜度可能是多少； * 采用哪些數據結構或算法思維，能把這個問題解決。 為了方便你理解，下面我們來舉一個例子，在一個包含 n 個元素的無序數組 a 中，輸出其最大值 max_val。 這個問題比較簡單。顯然，要輸出的最大值 max_val，也是原數組的元素之一。因此，這個問題的類型是，在數據中基于某個條件的查找問題。 關于查找問題，我們學習過二分查找，其復雜度是 O(logn)。但可惜的是，二分查找的條件是輸入數據有序，這里并不滿足。這就意味著，我們很難在 O(logn) 的復雜度下解決問題。 但是，繼續分析你會發現，某一個數字元素的值會直接影響最終結果。這是因為，假設前 n-1 個數字的最大值是 5，但最后一個數字的值是否大于 5，會直接影響最后的結果。這就意味著，這個問題不把所有的輸入數據全都過一遍，是無法得到正確答案的。要把所有數據全都過一遍，這就是 O(n) 的復雜度。 小結一下就是，因為該問題屬于查找問題，所以考慮用 O(logn) 的二分查找。但因為數組無序，導致它并不適用。又因為必須把全部數據過一遍，因此考慮用 O(n) 的檢索方法。這就是復雜度的下限。 當明確了復雜度的下限是 O(n) 后，你就能知道此時需要一層 for 循環去尋找最大值。那么循環的過程中，就可以實現動態維護一個最大值變量。空間復雜度是 O(1)，并不需要采用某些復雜的數據結構。這個問題我們在前面的課時 1 中寫過的代碼如下： ``` public void s1_3() { int a[] = { 1, 4, 3 }; int max_val = -1; int max_inx = -1; for (int i = 0; i < a.length; i++) { if (a[i] > max_val) { max_val = a[i]; max_inx = i; } } System.out.println(max_val); } ``` #### 通用解題的方法論 前面的例子只是一個簡單的熱身。在實際工作中，我們遇到的問題通常會更復雜多變。那么。面對這些問題是否有一些通用的解決方法呢？答案是有的。 面對一個未知問題時，你可以從復雜度入手。嘗試去分析這個問題的時間復雜度上限是多少，也就是復雜度再高能高到哪里。這就是不計任何時間、空間損耗，采用暴力求解的方法去解題。然后分析這個問題的時間復雜度下限是多少，也就是時間復雜度再低能低到哪里。這就是你寫代碼的目標。 接著，嘗試去定位問題。在分析出這兩個問題之后，就需要去設計合理的數據結構和運用合適的算法思維，從暴力求解的方法去逼近寫代碼的目標了。 在這里需要先定位問題，這個問題的類型就決定了采用哪種算法思維。 最后，需要對數據操作進行分析。例如：在這個問題中，需要對數據進行哪些操作（增刪查），數據之間是否需要保證順序或逆序？當分析出這些操作的步驟、頻次之后，就可以根據不同數據結構的特性，去合理選擇你所應該使用的那幾種數據結構了。 經過以上分析，我們對方法論進行提練，宏觀上的步驟總結為以下 4 步： 1. 復雜度分析。估算問題中復雜度的上限和下限。 2. 定位問題。根據問題類型，確定采用何種算法思維。 3. 數據操作分析。根據增、刪、查和數據順序關系去選擇合適的數據結構，利用空間換取時間。 4. 編碼實現。 這套方法適用于絕大多數的問題，在實戰中需要你靈活運用。 #### 案例 梳理完方法論之后，我們回過頭來再看一下以前的例子，看看采用方法論是如何分析題目并找到答案的。 例 1，在一個數組 a = [1, 3, 4, 3, 4, 1, 3] 中，找到出現次數最多的那個數字。如果并列存在多個，隨機輸出一個。 我們先來分析一下復雜度。假設我們采用最暴力的方法。利用雙層循環的方式計算： 1. 第一層循環，我們對數組中的每個元素進行遍歷； 2. 第二層循環，對于每個元素計算出現的次數，并且通過當前元素次數 time_tmp 和全局最大次數變量 time_max 的大小關系，持續保存出現次數最多的那個元素及其出現次數。 由于是雙層循環，這段代碼在時間方面的消耗就是 n*n 的復雜度，也就是 O(n2)。這段代碼我們在第 1 課時中的例子里講過，這里就不再贅述了。 接著，我們思考一下這段代碼最低的復雜度可能是多少？ 不難發現，這個問題的復雜度最低低不過 O(n)。這是因為某個數字的數值是完全有可能影響最終結果。例如，a = [1, 3, 4, 3, 4, 1]，隨機輸出 1、3、4 都可以。如果 a 中增加一個元素變成，a = [1, 3, 4, 3, 4, 1, 3, 1]，則結果為 1。 由此可見，這個問題必須至少要對全部數據遍歷一次，所以復雜度再低低不過 O(n)。 顯然，這個問題屬于在一個數組中，根據某個條件進行查找的問題。既然復雜度低不過 O(n)，我們也不用考慮采用二分查找了。此處是用不到任何算法思維。那么如何讓 O(n2) 的復雜度降低為 O(n) 呢？ 只有通過巧妙利用數據結構了。分析這個問題就可以發現，此時不需要關注數據順序。因此，棧、隊列等數據結構用到的可能性會很低。如果采用新的數據結構，增刪操作肯定是少不了的。而原問題就是查找類型的問題，所以查找的動作一定是非常高頻的。在我們學過的數據結構中，查找有優勢，同時不需要考慮數據順序的只有哈希表，因此可以很自然地想到用哈希表解決問題。 哈希表的結構是“key-value”的鍵值對，如何設計鍵和值呢？哈希表查找的 key，所以 key 一定存放的是被查找的內容，也就是原數組中的元素。數組元素有重復，但哈希表中 key 不能重復，因此只能用 value 來保存頻次。 分析到這里，所有解決方案需要用到的關鍵因素就出來了，我們總結為以下 2 點： 1. 預期的時間復雜度是 O(n)，這就意味著編碼采用一層的 for 循環，對原數組進行遍歷。 2. 數據結構需要額外設計哈希表，其中 key 是數組的元素，value 是頻次。這樣可以支持 O(1) 時間復雜度的查找動作。 因此，這個問題的代碼就是： ``` public void s2_4() { int a[] = { 1, 3, 4, 3, 4, 1, 3, 1 }; Map<Integer, Integer> d = new HashMap<>(); for (int i = 0; i < a.length; i++) { if (d.containsKey(a[i])) { d.put(a[i], d.get(a[i]) + 1); } else { d.put(a[i], 1); } } int val_max = -1; int time_max = 0; for (Integer key : d.keySet()) { if (d.get(key) > time_max) { time_max = d.get(key); val_max = key; } } System.out.println(val_max); } ``` 這個問題，我們在前面的課時中曾給出了答案。答案并不是最重要的，重要的是它背后的解題思路。這個思路可以運用在很多我們沒有遇到過的復雜問題中。例如下面的問題。 例 2，這個問題是力扣的經典問題，two sums。給定一個整數數組 arr 和一個目標值 target，請你在該數組中找出加和等于目標值的兩個整數，并返回它們在原數組中的下標。 你可以假設，原數組中沒有重復元素，而且有且只有一組答案。但是，數組中的元素只能使用一次。例如，arr = [1, 2, 3, 4, 5, 6]，target = 4。因為，arr[0] + arr[2] = 1 + 3 = 4 = target，則輸出 0，2。 首先，我們來分析一下復雜度。假設我們采用最暴力的方法，利用雙層循環的方式計算，步驟如下： 1. 第一層循環，我們對數組中的每個元素進行遍歷； 2. 第二層循環，對于第一層的元素與 target 的差值進行查找。 例如，第一層循環遍歷到了 1，第二層循環就需要查找 target - arr[0] = 4 - 1 = 3 是否在數組中。由于是雙層循環，這段代碼在時間方面的消耗就是 n*n 的復雜度，也就是 O(n2)。 接下來，我們看看下限。很顯然，某個數字是否存在于原數組對結果是有影響的。因此，復雜度再低低不過 O(n)。 這里的問題是在數組中基于某個條件去查找數據的問題。然而可惜的是原數組并非有序，因此采用二分查找的可能性也會很低。那么如何把 O(n2) 的復雜度降低到 O(n) 呢？路徑只剩下了數據結構。 在暴力的方法中，第二層循環的目的是查找 target - arr[i] 是否出現在數組中。很自然地就會聯想到可能要使用哈希表。同時，這個例子中對于數據處理的順序并不關心，棧或者隊列使用的可能性也會很低。因此，不妨試試如何用哈希表去降低復雜度。 既然是要查找 target - arr[i] 是否出現過，因此哈希表的 key 自然就是 target - arr[i]。而 value 如何設計呢？這就要看一下結果了，最終要輸出的是查找到的 arr[i] 和 target - arr[i] 在數組中的索引，因此 value 存放的必然是 index 的索引值。 基于上面的分析，我們就能找到解決方案，分析如下： 1. 預期的時間復雜度是 O(n)，這就意味著編碼采用一層的 for 循環，對原數組進行遍歷。 2. 數據結構需要額外設計哈希表，其中 key 是 target - arr[i]，value 是 index。這樣可以支持 O(1) 時間復雜度的查找動作。 因此，代碼如下： ``` private static int[] twoSum(int[] arr, int target) { Map<Integer, Integer> map = new HashMap<>(); for (int i = 0; i < arr.length; i++) { map.put(arr[i], i); } for (int i = 0; i < arr.length; i++) { int complement = target - arr[i]; if (map.containsKey(complement) && map.get(complement) != i) { return new int[] { map.get(complement), i }; } } return null; } ``` 在這段代碼中我們采用了兩個 for 循環，時間復雜度就是 O(n) + O(n) = O(n)。額外使用了 map，空間復雜度也是 O(n)。第一個 for 循環，把數組轉為字典，存放的是“數值 -index”的鍵值對。第二個 for 循環，在字典中依次判斷，target - arr[i] 是否出現過。如果它出現過，且不是它自己，則打印 target - arr[i] 和 arr[i] 的索引。 #### 總結 在開發前，一定要對問題的復雜度進行分析，做好技術選型。這就是定位問題的過程。只有把這個過程做好，才能更好地解決問題。 通過本課時的學習，常用的分析問題的方法有以下 4 種： 1. 復雜度分析。估算問題中復雜度的上限和下限。 2. 定位問題。根據問題類型，確定采用何種算法思維。 3. 數據操作分析。根據增、刪、查和數據順序關系去選擇合適的數據結構，利用空間換取時間。 4. 編碼實現。 其中前 3 個步驟，分別對應于這個課程的模塊 1 到模塊 3，這也是算法開發的基礎知識。有了這些知識，才能在實際問題中分析并拼裝出解決方案。 #### 練習題 最后，我們給出一個練習題。在這個課時案例 2 的 two sums 中，我們采用了兩個 for 循環去實現。那么，能否只使用一個 for 循環完成結果的查找呢？