通過前面課時的學習，相信你已經建立了利用數據結構去完成時空轉移的思想。接下來，你需要在理論思想的指導下靈活使用。其實，要想靈活使用數據結構，你需要先弄清楚數據在代碼中被處理、加工的最小單位動作，也就是數據結構的基本操作，有了這些動作之后，你就可以基于此去選擇更合適的數據結構了。本課時我們就先來學習數據處理的基本操作。 代碼對數據的處理 我們重溫一下上一課時的例子。在一個數組中找出出現次數最多的那個元素的數值。例如，輸入數組 a = [1,2,3,4,5,5,6] 中，只有 5 出現了兩次，其余都是 1 次。顯然 5 出現的次數最多，則輸出 5。為了降低時間復雜度，我們引入了 k-v 的字典的數據結構。那么問題來了，究竟是什么原因，促使我們想到了使用字典的數據結構呢？如果不使用字典，改為使用數組行不行呢？ 為了回答這些問題，我們先看一下究竟此處代碼需要對數據進行哪些操作。我們提到過，這段代碼處理數據的核心思路是： 第一步，根據原始數組計算每個元素出現的次數； 第二步，根據第一步的結果，找到出現次數最多的元素。 首先，我們來分析第一步統計出現次數的處理。此時，你還不知道應該采用什么數據結構。 對于每一次的循環，你得到了輸入數組中的某個元素 a[ i ] 。接著，你需要判斷這個元素在未知的數據結構中是否出現過： 如果出現了，就需要對出現的次數加 1。 如果沒有出現過，則把這個元素新增到未知數據結構中，并且把次數賦值為 1。 這里的數據操作包括以下 3 個。 查找： 看能否在數據結構中查找到這個元素，也就是判斷元素是否出現過。 新增： 針對沒有出現過的情況，新增這個元素。 改動： 針對出現過的情況，需要對這個元素出現的次數加 1。 接下來，我們一起分析第二步。訪問數據結構中的每個元素，找到次數最多的元素。這里涉及的數據操作很簡單，只有查找。 因此，這段代碼需要高頻使用查找的功能。此時，第一步的查找動作嵌套在 for 循環中，如果你的代碼不能在 O(1) 的時間復雜度內完成，則代碼整體的時間復雜度并沒有下降。而能在 O(1) 的時間復雜度內完成查找動作的數據結構，只有字典類型。這樣，外層 for 循環是 O(n) 的時間復雜度，內部嵌套的查找操作是 O(1) 的時間復雜度。整體計算下來，就仍然是 O(n) 的時間復雜度。字典的查找是通過鍵值對的匹配完成的，它可以在 O(1) 時間復雜度內，實現對數值條件查找。關于字典的內容，我們在后續的課程中會詳細解答。 現在，我們換個解決方案。假設采用兩個數組，分別按照對應順序記錄元素及其對應的出現次數。數組對于元素的查找只能逐一訪問，時間復雜度是 O(n)。也就是說，在 O(n) 復雜度的 for 循環中，又嵌套了 O(n) 復雜度的查找動作，所以時間復雜度是 O(n2)。因此，這里的數據結構，只能采用字典類型。 數據處理的基本操作 不管是數組還是字典，都需要額外開辟空間，對數據進行存儲。而且數據存儲的數量，與輸入的數據量一致。因此，消耗的空間復雜度相同，都是 O(n)。由前面的分析可見，同樣采用復雜的數據結構，消耗了 O(n) 的空間復雜度，其對時間復雜度降低的貢獻有可能不一樣。因此，我們必須要設計合理的數據結構，以達到降低時間損耗的目的。 而設計合理的數據結構，又要從問題本身出發，我們可以采用這樣的思考順序： 首先我們分析這段代碼到底對數據先后進行了哪些操作。 然后再根據分析出來的數據操作，找到合理的數據結構。 這樣我們就把數據處理的基本操作梳理了出來。今后，即使你遇到更復雜的問題，無非就是這些基本操作的疊加和組合。只要按照上述的邏輯進行思考，就可以輕松設計出合理的數據結構， 其實，代碼對數據處理的操作類型非常少。代碼對數據的處理就是代碼對輸入數據進行計算，得到結果并輸出的過程。數據處理的操作就是找到需要處理的數據，計算結果，再把結果保存下來。這個過程總結為以下操作： 找到要處理的數據。這就是按照某些條件進行查找。 把結果存到一個新的內存空間中。這就是在現有數據上進行新增。 把結果存到一個已使用的內存空間中。這需要先刪除內存空間中的已有數據，再新增新的數據。 經過對代碼的拆解，你會發現即便是很復雜的代碼，它對數據的處理也只有這 3 個基本操作，增、刪、查。只要你圍繞這 3 個數據處理的操作進行分析，就能得出解決問題的最優方案。常用的分析方法可以參考下面的 3 個步驟： 首先，這段代碼對數據進行了哪些操作？ 其次，這些操作中，哪個操作最影響效率，對時間復雜度的損耗最大？ 最后，哪種數據結構最能幫助你提高數據操作的使用效率？ 這 3 個步驟構成了設計合理數據結構的方法論。圍繞第一步和第二步的數據處理的操作，我會再補充一些例子幫助你理解。而第三個方面就需要你擁有足夠扎實的數據結構基礎知識了，我會在后面的課程中詳細討論。 數據操作與數據結構的案例 我們先來看一個關于查找的例子。查找，就是從復雜的數據結構中，找到滿足某個條件的元素。通常可從以下兩個方面來對數據進行查找操作： 根據元素的位置或索引來查找。 根據元素的數值特征來查找。 針對上述兩種情況，我們分別給出例子進行詳細介紹。 例 1，我們來看第二個例子，對于一個數組，找到數組中的第二個元素并輸出。 這個問題的處理很簡單。由于數組本身具有索引 index ，因此直接通過索引就能查找到其第二個元素。別忘了，數組的索引值是從 0 開始的，因此第二個元素的索引值是 1 。不難發現，因為有了 index 的索引，所以我們就可以直接進行查找操作來，這里的時間復雜度為 O(1)。 例 2，我們來看第二個例子，如果是鏈表，如何找到這個鏈表中的第二個元素并輸出呢？ 鏈表和數組一樣，都是 O(n) 空間復雜度的復雜數據結構。但其區別之一就是，數組有 index 的索引，而鏈表沒有。鏈表是通過指針，讓元素按某個自定義的順序“手拉手”連接在一起的。 既然是這樣，要查找其第二個元素，就必須要先知道第一個元素在哪里。以此類推，鏈表中某個位置的元素的查找，只能通過從前往后的順序逐一去查找。不難發現，鏈表因為沒有索引，只能“一個接一個”地按照位置條件查找，在這種情況下時間復雜度就是 O (n)。 例 3，我們再來看第三個例子，關于數值條件的查找。 我們要查找出，數據結構中數值等于 5 的元素是否存在。這次的查找，無論是數組還是鏈表都束手無策了。唯一的方法，也只有按照順序一個接一個地去判斷元素數值是否滿足等于 5 的條件。很顯然，這樣的查找方法時間復雜度是 O(n)。那么有沒有時間復雜度更低的方式呢？答案當然是：有。 在前面的課時中，我們遇到過要查找出數組中出現次數最多的元素的情況。我們采用的方法是，把數組轉變為字典，以保存元素及其出現次數的 k-v 映射關系。而在每次的循環中，都需要對當前遍歷的元素，去查找它是否在字典中出現過。這里就是很實際的按照元素數值查找的例子。如果借助字典的數據類型，這個例子的查找問題，就可以在 O(1) 的時間復雜度內完成了。 例 4，我們再來看第四個例子，關于復雜數據結構中新增數據，這里有兩個可能. 第一個是在這個復雜數據結構的最后，新增一條數據。 第二個是在這個復雜數據結構的中間某個位置，新增一條數據。 這兩個可能性的區別在于，新增了數據之后，是否會導致原有數據結構中數據的位置順序改變。接下來，我們分別來舉例說明。 在復雜數據結構中，新增一條數據。假設是在數據結構的最后新增數據。此時新增一條數據后，對原數據沒有產生任何影響。因此，執行的步驟是： 首先，通過查找操作找到數據結構中最后一個數據的位置； 接著，在這個位置之后，通過新增操作，賦值或者插入一條新的數據即可。 如果是在數據結構中間的某個位置新增數據，則會對插入元素的位置之后的元素產生影響，導致數據的位置依次加 1 。例如，對于某個長度為 4 的數組，在第二個元素之后插入一個元素。則修改后的數組中，原來的第一、第二個元素的位置不發生變化，第三個元素是新插入的元素，第四、第五個元素則是原來的第三、第四個元素。 我們再來看看刪除。在復雜數據結構中刪除數據有兩個可能： 第一個是在這個復雜數據結構的最后，刪除一條數據。 第二個是在這個復雜數據結構的中間某個位置，刪除一條數據。 這兩個可能性的區別在于，刪除了數據之后，是否會導致原有數據結構中數據的位置順序改變。由于刪除操作和新增操作高度類似，我們就不再舉詳細闡述了。 通過上述例子的學習之后，你就可以對它們進行組合，去玩轉更復雜的數據操作了，我們再來看一個例子。 例 5，在某個復雜數據結構中，在第二個元素之后新增一條數據。隨后再刪除第 1 個滿足數值大于 6 的元素。我們來試著分析這個任務的數據操作過程。這里有兩個步驟的操作： 第一步，在第二個元素之后新增一條數據。這里包含了查找和新增兩個操作，即查找第二個元素的位置，并在數據結構中間新增一條數據。 第二步，刪除第 1 個滿足數值大于 6 的元素。這里包含查找和刪除兩個操作，即查找出第 1 個數值大于 6 的元素的位置，并刪除這個位置的元素。 因此，總共需要完成的操作包括，按照位置的查找、新增和按照數據數值的查找、刪除。 總結 好的，這節課的內容就到這里了。這一節的內容在很多數據結構的課程中都是沒有的，這是因為大部分課程設計時，都普遍默認你已經掌握了這些知識。但是，這些知識恰恰又是你學習數據結構的根基。只有在充分了解問題、明確數據操作的方法之后，才能設計出更加高效的數據結構類型。 經過我們的分析，數據處理的基本操作只有 3 個，分別是增、刪、查。其中，增和刪又可以細分為在數據結構中間的增和刪，以及在數據結構最后的增和刪。區別就在于原數據的位置是否發生改變。查找又可以細分為按照位置條件的查找和按照數據數值特征的查找。幾乎所有的數據處理，都是這些基本操作的組合和疊加。 練習題 下面我們給出一道練習題。對于一個包含 5 個元素的數組，如果要把這個數組元素的順序翻轉過來。你可以試著分析該過程需要對數據進行哪些操作？ 在實際的工作中，如果你不知道該用什么數據結構的時候，就一定要回歸問題本源。從數據需要被處理的動作出發。只有明確了會有什么動作，才能找到最合適的解決方法。如果你在拆解數據處理的操作過程中遇到什么問題或者關于拆解有新的想法，歡迎在留言區和我分享。