第5章 優化時間和空間效率 5.1 面試官談效率 “通常針對一些senior dev的candidates會問一些關于時間、空間效率的問題，這能夠體現一個應聘者較好的編程素質和能力。” ——劉景勇（Autodesk，軟件工程師） “面試時一般會直接要求空間和時間復雜度，這兩者都很重要。” ——張珺（百度，高級軟件工程師） “我們有很多考查時間、空間效率這方面的問題。通常兩者都給應聘者限定，然后讓他給出解決方案。” ——張曉禹（百度，技術經理） “只要不是特別大的內存開銷，時間復雜度比較重要。因為改進時間復雜度對算法的要求更高。” ——吳斌（NVidia，Graphics Architect） “空間換時間還是時間換空間，這要看具體的題目了。對于普通的應用，一般是空間換時間，因為通常用戶更關心速度，而且一般有足夠的存儲空間允許這么做。但對于現在的一般嵌入式設備，很多時候空間換時間就不現實了，因為存儲空間太少了。” ——陳黎明（微軟，SDE II） 5.2 時間效率 由于每個人都希望軟件的響應時間盡量短一些，所以軟件公司都很重視軟件的時間性能，都會在發布軟件之前花不少精力做時間效率優化。這也就不難理解為什么很多公司的面試官都把代碼的時間效率當做一個考查重點。面試官除了考查應聘者的編程能力之外，還關注應聘者有沒有不斷優化效率、追求完美的態度和能力。 首先，我們的編程習慣對代碼的時間效率有很大影響。比如C/C++程序員要養成采用引用（或指針）傳遞復雜類型參數的習慣。如果采用值傳遞的方式，從形參到實參會產生一次復制操作。這樣的復制是多余的操作，我們應該盡量避免。再舉個例子，如果用C#做多次字符串的拼接操作，不要多次用String的+運算符來拼接字符串，因為這樣會產生很多String的臨時實例，造成時間和空間的浪費。更好的辦法是用StringBuilder的Append方法來完成字符串的拼接。如果我們平時不太注意這些影響代碼效率的細節，沒有養成好的編碼習慣，那么我們的代碼可能就會讓面試官大失所望。 其次，即使同一個算法用循環和遞歸兩種思路實現的時間效率可能會大不一樣。遞歸的本質是把一個大的復雜問題分解成兩個或者多個小的簡單的問題。如果小問題中有相互重疊的部分，那么直接用遞歸實現雖然代碼顯得很簡潔，但時間效率可能會非常差（詳細討論見本書2.4.2節）。對于這種類型的題目，我們可以用遞歸的思路來分析問題，但寫代碼的時候可以用數組（一維或者多維數組）來保存中間結果基于循環實現。絕大部分動態規劃算法的分析和代碼實現都是分這兩個步驟完成的。 再次，代碼的時間效率還能體現應聘者對數據結構和算法功底的掌握程度。同樣是查找，如果是順序查找需要O（n）的時間；如果輸入的是排序的數組則只需要O（logn）的時間；如果事先已經構造好了哈希表，那查找在O（1）時間就能完成。我們只有對常見的數據結構和算法都了然于胸，才能在需要的時候選擇合適的數據結構和算法來解決問題。 最后，應聘者在面試的時候要展示敏捷的思維能力和追求完美的激情。聽到題目的時候，我們一般很快就能想到最直觀的算法。這個最直觀的辦法很有可能不是最優的，但也不妨在第一時間告訴面試官，這樣面試官至少會覺得我們思維比較敏捷。我們想到幾種思路之后面試官可能仍然不滿意，還在提示我們有更好的辦法。這個時候我們一定不能輕言放棄，而要表現出積極思考的態度，努力從不同的角度去思考問題。有些題目很難，面試官甚至不期待應聘者在短短幾十分鐘里想出完美的解法，但他會希望應聘者能夠有激情、有耐心去嘗試新的思路，而不是碰到難題就退縮。在面試的時候，應聘者的態度和激情對最終的面試結果也有很重要的影響。 面試題29：數組中出現次數超過一半的數字 題目：數組中有一個數字出現的次數超過數組長度的一半，請找出這個數字。例如輸入一個長度為9的數組{1,2,3,2,2,2,5,4,2}。由于數字2在數組中出現了5次，超過數組長度的一半，因此輸出2。 看到這道題很多應聘者就會想要是這個數組是排序的數組就好了。如果是排好序的數組，那么我們就能很容易統計出每個數字出現的次數。題目給出的數組沒有說是排序的，因此我們需要先給它排序。排序的時間復雜度是O（nlogn）。最直觀的算法通常不是面試官滿意的算法，接下來我們試著找出更快的算法。 解法一：基于Partition函數的O（n）算法 如果我們回到題目本身仔細分析，就會發現前面的思路并沒有考慮到數組的特性：數組中有一個數字出現的次數超過了數組長度的一半。如果把這個數組排序，那么排序之后位于數組中間的數字一定就是那個出現次數超過數組長度一半的數字。也就是說，這個數字就是統計學上的中位數，即長度為n的數組中第n/2大的數字。我們有成熟的O（n）的算法得到數組中任意第k大的數字。 這種算法是受快速排序算法的啟發。在隨機快速排序算法中，我們先在數組中隨機選擇一個數字，然后調整數組中數字的順序，使得比選中的數字小數字都排在它的左邊，比選中的數字大的數字都排在它的右邊。如果這個選中的數字的下標剛好是n/2，那么這個數字就是數組的中位數。如果它的下標大于n/2，那么中位數應該位于它的左邊，我們可以接著在它的左邊部分的數組中查找。如果它的下標小于n/2，那么中位數應該位于它的右邊，我們可以接著在它的右邊部分的數組中查找。這是一個典型的遞歸過程，可以用如下代碼實現：  上述代碼中的函數Partition是完成快速排序的基礎。我們在本書的2.4.1節詳細討論了這個函數，這里不再重復。 在面試的時候，除了要完成基本功能即找到符合要求的數字之外，還要考慮一些無效的輸入。如果函數的輸入參數是一個指針（數組在參數傳遞的時候退化為指針），就要考慮這個指針可能為NULL。下面的函數CheckInvalidArray用來判斷輸入的數組是不是無效的。題目中說數組中有一個數字出現次數超過數組長度的一半，如果輸入的數組中出現頻率最高的數字都沒有達到這個標準那該怎么辦？這就是我們定義了一個CheckMoreThanHalf函數的原因。面試的時候我們要全面考慮這些情況，才能讓面試官完全滿意。下面的代碼用一個全局變量來表示輸入無效的情況。更多關于出錯處理的討論，詳見本書3.3節。  解法二：根據數組特點找出O（n）的算法 接下來我們從另外一個角度來解決這個問題。數組中有一個數字出現的次數超過數組長度的一半，也就是說它出現的次數比其他所有數字出現次數的和還要多。因此我們可以考慮在遍歷數組的時候保存兩個值：一個是數組中的一個數字，一個是次數。當我們遍歷到下一個數字的時候，如果下一個數字和我們之前保存的數字相同，則次數加1；如果下一個數字和我們之前保存的數字不同，則次數減1。如果次數為零，我們需要保存下一個數字，并把次數設為1。由于我們要找的數字出現的次數比其他所有數字出現的次數之和還要多，那么要找的數字肯定是最后一次把次數設為1時對應的數字。 下面是這種思路的參考代碼：  和第一種思路一樣，我們也要檢驗輸入的數組是不是有效的，這里不再重復。 解法比較 上述兩種算法的時間復雜度都是O（n）。基于Partition的算法的時間復雜度的分析不是很直觀，本書限于篇幅不作詳細討論，感興趣的讀者可以參考《算法導論》等書籍的相關章節。我們注意到在第一個解法中，需要交換數組中數字的順序，這就會修改輸入的數組。我們是不是可以修改輸入的數組呢？在面試的時候，我們可以和面試官討論，讓他明確需求。如果面試官說不能修改輸入的數組，那就只能采用第二種算法了。 源代碼： 本題完整的源代碼詳見29\_MoreThanHalfNumber項目。 測試用例： ● 功能測試（輸入的數組中存在一個出現次數超過數組長度一半的數字，輸入的數組中不存在一個出現次數超過數組長度一半的數字）。 ● 特殊輸入測試（輸入的數組中只有一個數字、輸入NULL指針）。 本題考點： ● 考查對時間復雜度的理解。應聘者每想出一種解法，面試官都期待他能分析出這種解法的時間復雜度是多少。 ● 考查思維的全面性。面試官除了要求應聘者能對有效的輸入返回正確的結果之外，同時也期待應聘者能對無效的輸入作相應的處理。 面試題30：最小的k個數 題目：輸入n個整數，找出其中最小的k個數。例如輸入4、5、1、6、2、7、3、8這8個數字，則最小的4個數字是1、2、3、4。 這道題最簡單的思路莫過于把輸入的n個整數排序，排序之后位于最前面的k個數就是最小的k個數。這種思路的時間復雜度是O（nlogn），面試官會提示我們還有更快的算法。 解法一：O（n）的算法，只有當我們可以修改輸入的數組時可用 從解決面試題29“數組中出現次數超過一半的數字”得到了啟發，我們同樣可以基于Partition函數來解決這個問題。如果基于數組的第k個數字來調整，使得比第k個數字小的所有數字都位于數組的左邊，比第k個數字大的所有數字都位于數組的右邊。這樣調整之后，位于數組中左邊的k個數字就是最小的k個數字（這k個數字不一定是排序的）。下面是基于這種思路的參考代碼：  采用這種思路是有限制的。我們需要修改輸入的數組，因為函數Partition會調整數組中數字的順序。如果面試官要求不能修改輸入的數組，我們該怎么辦呢？ 解法二：O（nlogk）的算法，特別適合處理海量數據 我們可以先創建一個大小為k的數據容器來存儲最小的k個數字，接下來我們每次從輸入的n個整數中讀入一個數。如果容器中已有的數字少于k個，則直接把這次讀入的整數放入容器之中；如果容器中已有k個數字了，也就是容器已滿，此時我們不能再插入新的數字而只能替換已有的數字。找出這已有的k個數中的最大值，然后拿這次待插入的整數和最大值進行比較。如果待插入的值比當前已有的最大值小，則用這個數替換當前已有的最大值；如果待插入的值比當前已有的最大值還要大，那么這個數不可能是最小的k個整數之一，于是我們可以拋棄這個整數。 因此當容器滿了之后，我們要做3件事情：一是在k個整數中找到最大數；二是有可能在這個容器中刪除最大數；三是有可能要插入一個新的數字。如果用一個二叉樹來實現這個數據容器，那么我們能在O（logk）時間內實現這三步操作。因此對于n個輸入數字而言，總的時間效率就是O（nlogk）。 我們可以選擇用不同的二叉樹來實現這個數據容器。由于每次都需要找到k個整數中的最大數字，我們很容易想到用最大堆。在最大堆中，根結點的值總是大于它的子樹中任意結點的值。于是我們每次可以在O（1）得到已有的k個數字中的最大值，但需要O（logk）時間完成刪除及插入操作。 我們自己從頭實現一個最大堆需要一定的代碼，這在面試短短的幾十分鐘內很難完成。我們還可以采用紅黑樹來實現我們的容器。紅黑樹通過把結點分為紅、黑兩種顏色并根據一些規則確保樹在一定程度上是平衡的，從而保證在紅黑樹中查找、刪除和插入操作都只需要O（logk）時間。在STL中set和multiset都是基于紅黑樹實現的。如果面試官不反對我們用STL中的數據容器，我們就可以直接拿過來用。下面是基于STL中的multiset的參考代碼：  解法比較 基于函數Partitiaon的第一種解法的平均時間復雜度是O（n），比第二種思路要快，但同時它也有明顯的限制，比如會修改輸入的數組。 第二種解法雖然要慢一點，但它有兩個明顯的優點。一是沒有修改輸入的數據（代碼中的變量data）。我們每次只是從data中讀入數字，所有的寫操作都是在容器leastNumbers中進行的。二是該算法適合海量數據的輸入（包括百度在內的多家公司非常喜歡與海量輸入數據相關的問題）。假設題目是要求從海量的數據中找出最小的k個數字，由于內存的大小是有限的，有可能不能把這些海量的數據一次性全部載入內存。這個時候，我們可以從輔助存儲空間（比如硬盤）中每次讀入一個數字，根據GetLeastNumbers的方式判斷是不是需要放入容器leastNumbers即可。這種思路只要求內存能夠容納leastNumbers即可，因此它最適合的情形就是n很大并且k較小的問題。 我們可以用表5.1總結這兩種解法的特點。 表5.1 兩種算法的特點比較  由于這兩種算法各有優缺點，各自適用于不同的場合，因此應聘者在動手做題之前先要問清楚題目的要求，包括輸入的數據量有多大、能否一次性載入內存、是否允許交換輸入數據中數字的順序等。 面試小提示： 如果面試時遇到的面試題有多種解法，并且每個解法都各有優缺點，那么我們要向面試官問清楚題目的要求，輸入的特點，從而選擇最合適的解法。 源代碼： 本題完整的源代碼詳見30\_KLeastNumbers項目。 測試用例： ● 功能測試（輸入的數組中有相同的數字，輸入的數組中沒有相同的數字）。 ● 邊界值測試（輸入的k等于1或者等于數組的長度） ● 特殊輸入測試（k小于1、k大于數組的長度、指向數組的指針為NULL）。 本題考點： ● 考查對時間復雜度的分析能力。面試的時候每想出一個解法，我們都要能分析出這種解法的時間復雜度是多少。 ● 如果采用第一種思路，本題考查對Partition函數的理解。這個函數既是快速排序的基礎，也可以用來查找n個數中第k大的數字。 ● 如果采用第二種思路，本題考查對堆、紅黑樹等數據結構的理解。當需要在某數據容器內頻繁查找及替換最大值時，我們要想到二叉樹是個合適的選擇，并能想到用堆或者紅黑樹等特殊的二叉樹來實現。 面試題31：連續子數組的最大和 題目：輸入一個整型數組，數組里有正數也有負數。數組中一個或連續的多個整數組成一個子數組。求所有子數組的和的最大值。要求時間復雜度為O（n）。 例如輸入的數組為{1,-2,3,10,-4,7,2,-5}，和最大的子數組為{3,10,-4,7,2}，因此輸出為該子數組的和18。 看到這道題，很多人都能想到最直觀的方法，即枚舉出數組的所有子數組并求出它們的和。一個長度為n的數組，總共有n（n＋1）/2個子數組。計算出所有子數組的和，最快也需要O（n2）的時間。通常最直觀的方法不會是最優的解法，面試官將提示我們還有更快的算法。 解法一：舉例分析數組的規律 我們試著從頭到尾逐個累加示例數組中的每個數字。初始化和為0。第一步加上第一個數字1，此時和為1。接下來第二步加上數字-2，和就變成了-1。第三步加上數字3。我們注意到由于此前累計的和是-1，小于0，那如果用-1加上3，得到的和是2，比3本身還小。也就是說從第一個數字開始的子數組的和會小于從第三個數字開始的子數組的和。因此我們不用考慮從第一個數字開始的子數組，之前累計的和也被拋棄。 我們從第三個數字重新開始累加，此時得到的和是3。接下來第四步加10，得到和為13。第五步加上-4，和為9。我們發現由于-4是一個負數，因此累加-4之后得到的和比原來的和還要小。因此我們要把之前得到的和13保存下來，它有可能是最大的子數組的和。第六步加上數字7，9加7的結果是16，此時和比之前最大的和13還要大，把最大的子數組的和由13更新為16。第七步加上2，累加得到的和為18，同時我們也要更新最大子數組的和。第八步加上最后一個數字-5，由于得到的和為13，小于此前最大的和18，因此最終最大的子數組的和為18，對應的子數組是{3,10,-4,7,2}。整個過程可以用表5.2總結如下： 表5.2 計算數組{1,-2,3,10,-4,7,2,-5}中子數組的最大和的過程  把過程分析清楚之后，我們就可以動手寫代碼了。下面是一段參考代碼：  面試的時候我們要考慮無效的輸入，比如輸入的數組參數為空指針、數組長度小于等于0等情況。此時我們讓函數返回什么數字？如果是返回0，那我們又怎么區分子數組的和的最大值是0和無效輸入這兩種不同情況呢？因此我們定義了一個全局變量來標記是否輸入無效。 解法二：應用動態規劃法 如果算法的功底足夠扎實，我們還可以用動態規劃的思想來分析這個問題。如果用函數f（i）表示以第i個數字結尾的子數組的最大和，那么我們需要求出max\[f（i）\]，其中0≤i<n。我們可用如下遞歸公式求f（i）：  這個公式的意義：當以第i－1個數字結尾的子數組中所有數字的和小于0時，如果把這個負數與第i個數累加，得到的結果比第i個數字本身還要小，所以這種情況下以第i個數字結尾的子數組就是第i個數字本身（如表5.2的第3步）。如果以第i－1個數字結尾的子數組中所有數字的和大于0，與第i個數字累加就得到以第i個數字結尾的子數組中所有數字的和。 雖然通常我們用遞歸的方式分析動態規劃的問題，但最終都會基于循環去編碼。上述公式對應的代碼和前面給出的代碼一致。遞歸公式中的f（i）對應的變量是nCurSum，而max\[f（i）\]就是nGreatestSum。因此可以說這兩種思路是異曲同工。 源代碼： 本題完整的源代碼詳見31\_GreatestSumOfSubarrays項目。 測試用例： ● 功能測試（輸入的數組中有正數也有負數，輸入的數組中全是正數，輸入的數組中全是負數）。 ● 特殊輸入測試（表示數組的指針為NULL指針）。 本題考點： ● 考查對時間復雜度的理解。這道題如果應聘者給出時間復雜度為O（n2）甚至O（n3）的算法，是不能通過面試的。 ● 考查對動態規劃的理解。如果應聘者熟練掌握了動態規劃算法，那么他就能輕松地找到解題方案。如果沒有想到用動態規劃的思想，那么應聘者就需要仔細地分析累加子數組的和的過程，從而找到解題的規律。 ● 考查思維的全面性。能否合理地處理無效的輸入，對面試結果有很重要的影響。 面試題32：從1到n整數中1出現的次數 題目：輸入一個整數n，求從1到n這n個整數的十進制表示中1出現的次數。例如輸入12，從1到12這些整數中包含1 的數字有1，10，11和12，1一共出現了5次。 不考慮時間效率的解法，靠它想拿Offer有點難 如果在面試的時候碰到這個問題，應聘者大多能想到最直觀的方法，也就是累加1到n中每個整數1出現的次數。我們可以每次通過對10求余數判斷整數的個位數字是不是1。如果這個數字大于10，除以10之后再判斷個位數字是不是1。基于這個思路，我們不難寫出如下代碼：  在上述思路中，我們對每個數字都要做除法和求余運算以求出該數字中1出現的次數。如果輸入數字n，n有O（logn）位，我們需要判斷每一位是不是1，那么它的時間復雜度是O（n\*logn）。當輸入n非常大的時候，需要大量的計算，運算效率不高。面試官不會滿意這種算法，我們仍然需要努力。 從數字規律著手明顯提高時間效率的解法，能讓面試官耳目一新 如果希望不用計算每個數字的1的個數，那就只能去尋找1在數字中出現的規律了。為了找到規律，我們不妨用一個稍微大一點的數字比如21345作為例子來分析。我們把從1到21345的所有數字分為兩段，一段是從1到1345，另一段是從1346到21345。 我們先看從1346到21345中1出現的次數。1的出現分為兩種情況。首先分析1出現在最高位（本例中是萬位）的情況。從1346到21345的數字中，1出現在10000～19999這10000個數字的萬位中，一共出現了10000（104）個。 值得注意的是，并不是對所有5位數而言在萬位出現的次數都是10000個。對于萬位是1的數字比如輸入12345，1只出現在10000～12345的萬位，出現的次數不是104次，而是2346次，也就是除去最高數字之后剩下的數字再加上1（即2345＋1=2346次）。 接下來分析1出現在除最高位之外的其他四位數中的情況。例子中1346～21345這20000個數字中后4位中1出現的次數是2000次。由于最高位是2，我們可以再把1346～21345分成兩段，1346～11345和11346～21345。每一段剩下的4位數字中，選擇其中一位是1，其余三位可以在0～9這10個數字中任意選擇，因此根據排列組合原則，總共出現的次數是2×103=2000次。 至于從1到1345中1出現的次數，我們就可以用遞歸求得了。這也是我們為什么要把1～21345分成1～1345和1346～21345兩段的原因。因為把21345的最高位去掉就變成1345，便于我們采用遞歸的思路。 基于前面的分析，我們可以寫出如下代碼（為了編程方便，我們先把數字轉換成字符串）：  這種思路是每次去掉最高位做遞歸，遞歸的次數和位數相同。一個數字n有O（logn）位，因此這種思路的時間復雜度是O（logn），比前面的原始方法要好很多。 源代碼： 本題完整的源代碼詳見32\_NumberOf1項目。 測試用例： ● 功能測試（輸入5、10、55、99等）。 ● 邊界值測試（輸入0、1等）。 ● 性能測試（輸入較大的數字如10000、21235等）。 本題考點： ● 考查應聘者做優化的激情和能力。最原始的方法大部分應聘者都能想到。當面試官提示還有更快的方法之后，應聘者千萬不要輕易放棄嘗試。雖然想出O（logn）的方法不容易，但應聘者要展示自己追求更快算法的激情，多嘗試不同的方法，必要的時候可以要求面試官給出提示，但不能輕易說自己想不出來并且放棄努力。 ● 考查面應聘者對復雜問題的思維能力。要想找到O（logn）的方法，應聘者需要有很嚴密的數學思維能力，并且還要通過分析具體例子一步步找到通用的規律。這些能力在實際工作中面對復雜問題的時候都非常有用。 面試題33：把數組排成最小的數 題目：輸入一個正整數數組，把數組里所有數字拼接起來排成一個數，打印能拼接出的所有數字中最小的一個。例如輸入數組{3,32,321}，則打印出這3個數字能排成的最小數字321323。 這個題目最直接的做法應該是先求出這個數組中所有數字的全排列，然后把每個排列拼起來，最后求出拼起來的數字的最大值。求數組的排列和面試題28“字符串的排列”非常類似，這里不再詳細介紹。根據排列組合的知識，n個數字總共有n!個排列。我們再來看一種更快的算法。 這道題其實是希望我們能找到一個排序規則，數組根據這個規則排序之后能排成一個最小的數字。要確定排序規則，就要比較兩個數字，也就是給出兩個數字m和n，我們需要確定一個規則判斷m和n哪個應該排在前面，而不是僅僅比較這兩個數字的值哪個更大。 根據題目的要求，兩個數字m和n能拼接成數字mn和nm。如果mn<nm，那么我們應該打印出mn，也就是m應該排在n的前面，我們定義此時m小于n；反之，如果nm<mn，我們定義n小于m。如果mn=nm，m等于n。在下文中，符號“<”、“>”及“=”表示常規意義的數值的大小關系，而文字“大于”、“小于”、“等于”表示我們新定義的大小關系。 接下來考慮怎么去拼接數字，即給出數字m和n，怎么得到數字mn和nm并比較它們的大小。直接用數值去計算不難辦到，但需要考慮到一個潛在的問題就是m和n都在int能表達的范圍內，但把它們拼起來的數字mn和nm用int表示就有可能溢出了，所以這還是一個隱形的大數問題。 一個非常直觀的解決大數問題的方法就是把數字轉換成字符串。另外，由于把數字m和n拼接起來得到mn和nm，它們的位數肯定是相同的，因此比較它們的大小只需要按照字符串大小的比較規則就可以了。 基于這個思路，我們可以寫出如下代碼：  在上述代碼中，我們先把數組中的整數轉換成字符串，在函數compare中定義比較規則，并根據該規則用庫函數qsort排序。最后把排好序的數組中的數字依次打印出來，就是該數組中數字能拼接出來的最小數字。這種思路的時間復雜度和qsort的時間復雜度相同，也就是O（nlogn），這比用n!的時間求出所有排列的思路要好很多。 上述思路中，我們定義了一種新的比較兩個數的規則，這種規則是不是有效的？另外，我們只是定義了比較兩個數的規則，卻用它來排序一個含有多個數字的數組，最終拼接數組中的所有數字得到的是不是真的就是最小的數字？一些嚴格的面試官還會要求我們給出嚴格的數學證明，以確保我們的解決方案是正確的。 我們首先證明之前定義的比較兩個數字大小的規則是有效的。一個有效的比較規則需要3個條件：自反性、對稱性和傳遞性。我們分別予以證明。 （1）自反性：顯然有aa=aa，所以a等于a。 （2）對稱性：如果a小于b，則ab<ba，所以ba>ab，因此b大于a。 （3）傳遞性：如果a小于b，則ab<ba。假設a和b用十進制表示時分別有l位和m位，于是ab=a×10m＋b，ba=b×10l＋a。 ab<ba→a×10m＋b<b×10l＋a→a×10m－a< b×10l－b →a（10m－1）<b（10l－1）→a/（10l－1）<b/（10m－1） 同時如果b小于c，則bc<cb。假設c用十進制表示是有n位，和前面的證明過程一樣，可以得到b/（10m－1）<c/（10n－1）。 a/（10l－1）<b/（10m－1）并且b/（10m－1）<c/（10n－1）→a/（10l－1）<c/（10n－1）→a（10n－1）<c（10l－1） →a×10n＋c<c×10l＋a→ac<ca→a小于c 于是我們證明了這種比較規則滿足自反性、對稱性和傳遞性，是一種有效的比較規則。接下來我們證明根據這種比較規則把數組排序之后，把數組中的所有數字拼接起來得到的數字的確是最小的。直接證明不是很容易，我們不妨用反證法來證明。 我們把n個數按照前面的排序規則排序之后，表示為A1A2A3…An。假設這樣拼接出來的數字并不是最小的，即至少存在兩個x和y（0<x<y<n），交換第x個數和第y個數后，A1A2…Ay…Ax…An<A1A2…Ax…Ay…An。 由于A1A2…Ax…Ay…An是按照前面的規則排好的序列，所以有Ax小于Ax＋1小于Ax＋2小于…小于Ay－2小于Ay－1小于Ay。 由于Ay－1小于Ay，所以Ay－1Ay<AyAy－1。我們在序列A1A2…Ax…Ay－1Ay…An中交換Ay－1和Ay，有A1A2…Ax…Ay－1Ay…An<A1A2…Ax…AyAy－1…An（這個實際上也需要證明，感興趣的讀者可以自己試著證明）。我們就這樣一直把Ay和前面的數字交換，直到和Ax交換為止。于是就有A1A2…Ax…Ay－1Ay…An<A1A2…Ax…AyAy－1…An<A1A2…Ax…AyAy－2Ay－1…An<…<A1A2…AyAx…Ay－2Ay－1…An。 同理由于Ax小于Ax＋1，所以AxAx＋1<Ax＋1Ax。我們在序列A1A2…AyAxAx＋1…Ay－2Ay－1…An中只交換Ax和Ax＋1，有A1A2…AyAxAx＋1…Ay－2Ay－1…An<A1A2…AyAx＋1Ax…Ay－2Ay－1…An。我們接下來一直拿Ax和它后面的數字交換，直到和Ay－1交換為止。于是就有A1A2…AyAxAx＋1…Ay－2Ay－1…An<A1A2…AyAx＋1Ax…Ay－2Ay－1…An<…<A1A2…AyAx＋1Ax＋2…Ay－2Ay－1Ax…An。 所以A1A2…Ax…Ay…An<A1A2…Ay…Ax…An，這和我們的假設的A1A2…Ay…Ax…An<A1A2…Ax…Ay…An相矛盾。 所以假設不成立，我們的算法是正確的。 源代碼： 本題完整的源代碼詳見33\_SortArrayForMinNumber項目。 測試用例： ● 功能測試（輸入的數組中有多個數字，輸入的數組中的數字有重復的數位，輸入的數字只有一個數字）。 ● 特殊輸入測試（表示數組的指針為NULL指針）。 本題考點： ● 本題有兩個難點；第一個難點是想出一種新的比較規則來排序一個數組；第二個難點在于證明這個比較規則是有效的，并且證明根據這個規則排序之后把數組中所有數字拼接起來得到的數字是最小的。要想解決這兩個難點，都要求應聘者有很強的數學功底和邏輯思維能力。 ● 考查解決大數問題的能力。應聘者在面試的時候要意識到，把兩個int型的整數拼接起來得到的數字可能會超出int型數字能夠表達的范圍，從而導致數字溢出。我們可以用字符串表示數字，這樣就能簡潔地解決大數問題。 5.3 時間效率與空間效率的平衡 硬件的發展一直遵循著摩爾定律，內存的容量基本上每隔18個月就會翻一番。由于內存的容量增加迅速，在軟件開發的過程中我們允許以犧牲一定的空間為代碼來優化時間性能，以盡可能地縮短軟件的響應時間。這就是我們通常所說的“以空間換時間”。 在面試的時候，如果我們分配少量的輔助空間來保存計算的中間結果以提高時間效率，這樣的思路通常是可以接受的。本書中收集的面試題中有不少這種類型的題目，比如在面試題34“丑數”中用一個數組按照從小到大的順序保存已經求出的丑數；在面試題43“n個骰子的點數”中交替使用兩個數組求骰子每個點數出現的次數。 值得注意的是，“以時間換空間”的策略并不一定都是可行的，在面試的時候要具體問題具體分析。我們都知道在n個無序的元素里做查找操作，需要O（n）的時間。但如果我們把這些元素放進一個哈希表，那么在哈希表內就能實現O（1）的查找。但同時實現一個哈希表是有空間消耗的，是不是值得以多消耗空間為前提來換取時間性能的提升，我們需要根據實際情況仔細權衡。在面試題35“第一個只出現一次的字符”中，我們用數組實現了一個簡易哈希表，有了這個哈希表就能實現O（1）查找任意字符。對于ASCII碼的字符而言，總共只有256個字符，因此只需要1K的輔助內存。這點內存消耗對于絕大多數硬件來說是完全可以接受的。但如果是16位的Unicode的字符，創建這樣一個長度為216的整型數組需要4×216也就是256K的內存。這對于個人電腦來說也是可以接受的，但對于一些嵌入式的開發就要慎重了。 很多時候時間效率和空間效率存在類似于魚與熊掌的關系，我們需要在它們之間有所取舍。在面試的時候究竟是“以時間換空間”還是“以空間換時間”，我們可以和面試官進行探討。多和面試官進行這方面的討論是很有必要的，這既能顯示我們的溝通能力，又能展示我們對軟件性能全方位的把握能力。 面試題34：丑數 題目：我們把只包含因子2、3和5的數稱作丑數（Ugly Number）。求按從小到大的順序的第1500個丑數。例如6、8都是丑數，但14不是，因為它包含因子7。習慣上我們把1當做第一個丑數。 逐個判斷每個整數是不是丑數的解法，直觀但不夠高效 所謂一個數m是另一個數n的因子，是指n能被m整除，也就是n%m＝0。根據丑數的定義，丑數只能被2、3和5整除。也就是說如果一個數能被2整除，我們把它連續除以2；如果能被3整除，就連續除以3；如果能被5整除，就除以連續5。如果最后我們得到的是1，那么這個數就是丑數，否則不是。 因此我們可以寫出下面的函數來判斷一個數是不是丑數：  接下來，我們只需要按照順序判斷每一個整數是不是丑數，即：  我們只需要在函數GetUglyNumber中傳入參數1500，就能得到第1500個丑數。該算法非常直觀，代碼也非常簡潔，但最大的問題每個整數都需要計算。即使一個數字不是丑數，我們還是需要對它做求余數和除法操作。因此該算法的時間效率不是很高，面試官也不會就此滿足，他會提示我們還有更高效的算法。 創建數組保存已經找到的丑數，用空間換時間的解法 前面的算法之所以效率低，很大程度上是因為不管一個數是不是丑數我們對它都要作計算。接下來我們試著找到一種只要計算丑數的方法，而不在非丑數的整數上花費時間。根據丑數的定義，丑數應該是另一個丑數乘以2、3或者5的結果（1除外）。因此我們可以創建一個數組，里面的數字是排好序的丑數，每一個丑數都是前面的丑數乘以2、3或者5得到的。 這種思路的關鍵在于怎樣確保數組里面的丑數是排好序的。假設數組中已經有若干個丑數排好序后存放在數組中，并且把已有最大的丑數記做M，我們接下來分析如何生成下一個丑數。該丑數肯定是前面某一個丑數乘以2、3或者5的結果，所以我們首先考慮把已有的每個丑數乘以2。在乘以2的時候，能得到若干個小于或等于M的結果。由于是按照順序生成的，小于或者等于M肯定已經在數組中了，我們不需再次考慮；還會得到若干個大于M的結果，但我們只需要第一個大于M的結果，因為我們希望丑數是按從小到大的順序生成的，其他更大的結果以后再說。我們把得到的第一個乘以2后大于M的結果記為M2。同樣，我們把已有的每一個丑數乘以3和5，能得到第一個大于M的結果M3和M5。那么下一個丑數應該是M2、M3和M5這3個數的最小者。 前面分析的時候，提到把已有的每個丑數分別都乘以2、3和5。事實上這不是必須的，因為已有的丑數是按順序存放在數組中的。對乘以2而言，肯定存在某一個丑數T2，排在它之前的每一個丑數乘以2得到的結果都會小于已有最大的丑數，在它之后的每一個丑數乘以2得到的結果都會太大。我們只需記下這個丑數的位置，同時每次生成新的丑數的時候，去更新這個T2。對乘以3和5而言，也存在著同樣的T3和T5。 有了這些分析，我們就可以寫出如下代碼：  和第一種思路相比，第二種思路不需要在非丑數的整數上做任何計算，因此時間效率有明顯提升。但也需要指出，第二種算法由于需要保存已經生成的丑數，因此需要一個數組，從而增加了空間消耗。如果是求第1500個丑數，將創建一個能容納1500個丑數的數組，這個數組占內存6KB。而第一種思路沒有這樣的內存開銷。總的來說，第二種思路相當于用較小的空間消耗換取了時間效率的提升。 源代碼： 本題完整的源代碼詳見34\_UglyNumber項目。 測試用例： ● 功能測試（輸入2、3、4、5、6等）。 ● 特殊輸入測試（邊界值1、無效輸入0）。 ● 性能測試（輸入較大的數字，如1500）。 本題考點： ● 考查應聘者對時間復雜度的理解。絕大部分應聘者都能想出第一種思路。在面試官提示還有更快的解法之后，應聘者能否分析出時間效率的瓶頸，并找出解決方案，是能否通過這輪面試的關鍵。 ● 考查應聘者的學習能力和溝通能力。丑數對很多人而言是個新概念。有些面試官喜歡在面試的時候定義一個新概念，然后針對這個新概念出面試題。這就要求應聘者聽到不熟悉的概念之后，要有主動積極的態度，大膽向面試官提問，經過幾次思考、提問、再思考的循環，在短時間內理解這個新概念。這個過程就體現了應聘者的學習能力和溝通能力。 面試題35：第一個只出現一次的字符 題目：在字符串中找出第一個只出現一次的字符。如輸入"abaccdeff"，則輸出'b'。 看到這道題時，我們最直觀的想法是從頭開始掃描這個字符串中的每個字符。當訪問到某字符時拿這個字符和后面的每個字符相比較，如果在后面沒有發現重復的字符，則該字符就是只出現一次的字符。如果字符串有n個字符，每個字符可能與后面的O（n）個字符相比較，因此這種思路的時間復雜度是O（n2）。面試官不會滿意這種思路，他會提示我們還有更快的方法。 由于題目與字符出現的次數相關，我們是不是可以統計每個字符在該字符串中出現的次數？要達到這個目的，我們需要一個數據容器來存放每個字符的出現次數。在這個數據容器中可以根據字符來查找它出現的次數，也就是說這個容器的作用是把一個字符映射成一個數字。在常用的數據容器中，哈希表正是這個用途。 為了解決這個問題，我們可以定義哈希表的鍵值（Key）是字符，而值（Value）是該字符出現的次數。同時我們還需要從頭開始掃描字符串兩次。第一次掃描字符串時，每掃描到一個字符就在哈希表的對應項中把次數加1。接下來第二次掃描時，每掃描到一個字符就能從哈希表中得到該字符出現的次數。這樣第一個只出現一次的字符就是符合要求的輸出。 哈希表是一種比較復雜的數據結構，并且C++的標準模板庫中沒有實現哈希表。接下來我們要考慮的問題就是如何實現哈希表。由于本題的特殊性，我們只需要一個非常簡單的哈希表就能滿足要求。字符（char）是一個長度為8的數據類型，因此總共有256 種可能。于是我們創建一個長度為256的數組，每個字母根據其ASCII碼值作為數組的下標對應數組的一個數字，而數組中存儲的是每個字符出現的次數。這樣我們就創建了一個大小為256，以字符ASCII碼為鍵值的哈希表。 第一次掃描時，在哈希表中更新一個字符出現的次數的時間是O（1）。如果字符串長度為n，那么第一次掃描的時間復雜度是O（n）。第二次掃描時，同樣O（1）能讀出一個字符出現的次數，所以時間復雜度仍然是O（n）。這樣算起來，總的時間復雜度是O（n）。同時，我們需要一個包含256個字符的輔助數組，它的大小是1K。由于這個數組的大小是個常數，因此可以認為這種算法的空間復雜度是O（1）。 當我們向面試官講述清楚這個思路并得到面試官的首肯之后，就可以動手寫代碼了。下面是一段參考代碼：  源代碼： 本題完整的源代碼詳見35\_FirstNotRepeatingChar項目。 測試用例： ● 功能測試（字符串中存在只出現一次的字符，字符串中不存在只出現一次字符，字符串中所有字符都只出現一次）。 ● 特殊輸入測試（字符串為NULL指針）。 本題考點： ● 考查對數組、字符串的編程能力。 ● 考查對哈希表的理解及運用。 ● 考查對時間效率及空間效率的分析能力。當面試官提示最直觀的算法不是最優解的時候，應聘者需要立即分析出這種算法的時間效率。在想出基于哈希表的算法之后，應聘者也應該分析出該方法的時間效率和空間效率分別是O（n）和O（1）。 本題擴展： 在前面的例子中，我們之所以可以把哈希表的大小設為256，是因為字符（char）是8個bit的類型，總共只有256個字符。但實際上字符不只是256個，比如中文就有幾千個漢字。如果題目要求考慮漢字，前面的算法是不是有問題？如果有，可以怎么解決？ 相關題目： ● 定義一個函數，輸入兩個字符串，從第一個字符串中刪除在第二個字符串中出現過的所有字符。例如從第一個字符串"We are students."中刪除在第二個字符串"aeiou"中出現過的字符得到的結果是"W r Stdnts. "。為了解決這個問題，我們可以創建一個用數組實現的簡單哈希表來存儲第二個字符串。這樣我們從頭到尾掃描第一個字符串的每一個字符時，用O（1）時間就能判斷出該字符是不是在第二個字符中。如果第一個字符串的長度是n，那么總的時間復雜度是O（n）。 ● 定義一個函數，刪除字符串中所有重復出現的字符。例如輸入"google"，刪除重復的字符之后的結果是"gole"。這個題目和上面的問題比較類似，我們可以創建一個用布爾型數組實現的簡單的哈希表。數組中的元素的意義是其下標看做ASCII碼后對應的字母在字符串中是否已經出現。我們先把數組中所有的元素都設為false。以"google"為例，當掃描到第一個g時，g的ASCII碼是103，那么我們把數組中下標為103的元素設為true。當掃描到第二個g時，我們發現數組中下標為103的元素的值是true，就知道g在前面已經出現了。也就是說，我們用O（1）時間就能判斷出每個字符是否在前面已經出現過。如果字符串的長度是n，那么總的時間復雜度是O（n）。 ● 在英語中，如果兩個單詞中出現的字母相同，并且每個字母出現的次數也相同，那么這兩個單詞互為變位詞（Anagram）。例如silent與listen、evil與live等互為變位詞。請完成一個函數，判斷輸入的兩個字符串是不是互為變位詞。我們可以創建一個用數組實現的簡單哈希表，用來統計字符串中每個字符出現的次數。當掃描到第一個字符串中的每個字符時，為哈希表對應的項的值增加1。接下來掃描第二個字符串，掃描到每個字符時，為哈希表對應的項的值減去1。如果掃描完第二個字符串后，哈希表中所有的值都是0，那么這兩個字符串就互為變位詞。 舉一反三： 如果需要判斷多個字符是不是在某個字符串里出現過或者統計多個字符在某個字符串中出現的次數，我們可以考慮基于數組創建一個簡單的哈希表。這樣可以用很小的空間消耗換來時間效率的提升。 面試題36：數組中的逆序對 題目：在數組中的兩個數字如果前面一個數字大于后面的數字，則這兩個數字組成一個逆序對。輸入一個數組，求出這個數組中的逆序對的總數。 例如在數組{7,5,6,4}中，一共存在5個逆序對，分別是（7,6）、（7,5）、（7,4）、（6,4）和（5,4）。 看到這個題目，我們的第一反應是順序掃描整個數組。每掃描到一個數字的時候，逐個比較該數字和它后面的數字的大小。如果后面的數字比它小，則這兩個數字就組成了一個逆序對。假設數組中含有n個數字。由于每個數字都要和O（n）個數字作比較，因此這個算法的時間復雜度是O（n2）。我們再嘗試找找更快的算法。 我們以數組{7,5,6,4}為例來分析統計逆序對的過程。每次掃描到一個數字的時候，我們不能拿它和后面的每一個數字作比較，否則時間復雜度就是O（n2），因此我們可以考慮先比較兩個相鄰的數字。 如圖5.1（a）和圖5.1（b）所示，我們先把數組分解成兩個長度為2的子數組，再把這兩個子數組分別拆分成兩個長度為1的子數組。接下來一邊合并相鄰的子數組，一邊統計逆序對的數目。在第一對長度為1的子數組{7}、{5}中7大于5，因此（7,5）組成一個逆序對。同樣在第二對長度為1的子數組{6}、{4}中也有逆序對（6,4）。由于我們已經統計了這兩對子數組內部的逆序對，因此需要把這兩對子數組排序（圖5.1（c）所示），以免在以后的統計過程中再重復統計。  圖5.1 統計數組{7,5,6,4}中逆序對的過程 注：圖中省略了最后一步，即復制第二個子數組最后剩余的4到輔助數組中。（a）P1指向的數字大于P2指向的數字，表明數組中存在逆序對。P2指向的數字是第二個子數組的第二個數字，因此第二個子數組中有兩個數字比7小。把逆序對數目加2，并把7復制到輔助數組，向前移動P1和P3。（b）P1指向的數字小于P2指向的數字，沒有逆序對。把P2指向的數字復制到輔助數組，并向前移動P2和P3。（c）P1指向的數字大于P2指向的數字，因此存在逆序對。由于P2指向的數字是第二個子數組的第一個數字，子數組中只有一個數字比5小。把逆序對數目加1，并把5復制到輔助數組，向前移動P1和P3。 接下來我們統計兩個長度為2的子數組之間的逆序對。我們在圖5.2中細分圖5.1（d）的合并子數組及統計逆序對的過程。  圖5.2 圖5.1（d）中合并兩個子數組并統計逆序對的過程 我們先用兩個指針分別指向兩個子數組的末尾，并每次比較兩個指針指向的數字。如果第一個子數組中的數字大于第二個子數組中的數字，則構成逆序對，并且逆序對的數目等于第二個子數組中剩余數字的個數（如圖5.2（a）和圖5.2（c）所示）。如果第一個數組中的數字小于或等于第二個數組中的數字，則不構成逆序對（如圖5.2（b）所示）。每一次比較的時候，我們都把較大的數字從后往前復制到一個輔助數組中去，確保輔助數組中的數字是遞增排序的。在把較大的數字復制到輔助數組之后，把對應的指針向前移動一位，接下來進行下一輪比較。 經過前面詳細的討論，我們可以總結出統計逆序對的過程：先把數組分隔成子數組，先統計出子數組內部的逆序對的數目，然后再統計出兩個相鄰子數組之間的逆序對的數目。在統計逆序對的過程中，還需要對數組進行排序。如果對排序算法很熟悉，我們不難發現這個排序的過程實際上就是歸并排序。我們可以基于歸并排序寫出如下代碼：   我們知道歸并排序的時間復雜度是O（nlogn），比最直觀的O（n2）要快，但同時歸并排序需要一個長度為n的輔助數組，相當于我們用O（n）的空間消耗換來了時間效率的提升，因此這是一種用空間換時間的算法。 源代碼： 本題完整的源代碼詳見36\_InversePairs項目。 測試用例： ● 功能測試（輸入未經排序的數組、遞增排序的數組、遞減排序的數組，輸入的數組中包含重復的數字）。 ● 邊界值測試（輸入的數組中只有兩個數字、數組的數組只有一個數字） ● 特殊輸入測試（表示數組的指針為NULL指針）。 本題考點： ● 考查分析復雜問題的能力。統計逆序對的過程很復雜，如何發現逆序對的規律，是應聘者解決這個題目的關鍵。 ● 考查應聘者對歸并排序的掌握程度。如果應聘者在分析統計逆序對的過程中發現問題與歸并排序的相似性，并能基于歸并排序形成解題思路，那通過這輪面試的幾率就很高了。 面試題37：兩個鏈表的第一個公共結點 題目：輸入兩個鏈表，找出它們的第一個公共結點。鏈表結點定義如下：  面試的時候碰到這道題，很多應聘者的第一反應就是蠻力法：在第一鏈表上順序遍歷每個結點，每遍歷到一個結點的時候，在第二個鏈表上順序遍歷每個結點。如果在第二個鏈表上有一個結點和第一個鏈表上的結點一樣，說明兩個鏈表在這個結點上重合，于是就找到了它們的公共結點。如果第一個鏈表的長度為m，第二個鏈表的長度為n，顯然該方法的時間復雜度是O（mn）。 通常蠻力法不會是最好的辦法，我們接下來試著分析有公共結點的兩個鏈表有哪些特點。從鏈表結點的定義可以看出，這兩個鏈表是單向鏈表。如果兩個單向鏈表有公共的結點，那么這兩個鏈表從某一結點開始，它們的m\_pNext都指向同一個結點。但由于是單向鏈表的結點，每個結點只有一個m\_pNext，因此從第一個公共結點開始，之后它們所有結點都是重合的，不可能再出現分叉。所以兩個有公共結點而部分重合的鏈表，拓撲形狀看起來像一個Y，而不可能像X（如圖5.3所示）。  圖5.3 兩個鏈表在值為6的結點處交匯 經過分析我們發現，如果兩個鏈表有公共結點，那么公共結點出現在兩個鏈表的尾部。如果我們從兩個鏈表的尾部開始往前比較，最后一個相同的結點就是我們要找的結點。可問題是在單向鏈表中，我們只能從頭結點開始按順序遍歷，最后才能到達尾結點。最后到達的尾結點卻要最先被比較，這聽起來是不是像“后進先出”？于是我們就能想到用棧的特點來解決這個問題：分別把兩個鏈表的結點放入兩個棧里，這樣兩個鏈表的尾結點就位于兩個棧的棧頂，接下來比較兩個棧頂的結點是否相同。如果相同，則把棧頂彈出接著比較下一個棧頂，直到找到最后一個相同的結點。 在上述思路中，我們需要用兩個輔助棧。如果鏈表的長度分別為m和n，那么空間復雜度是O（m＋n）。這種思路的時間復雜度也是O（m＋n）。和最開始的蠻力法相比，時間效率得到了提高，相當于是用空間消耗換取了時間效率。 之所以需要用到棧，是因為我們想同時遍歷到達兩個棧的尾結點。當兩個鏈表的長度不相同時，如果我們從頭開始遍歷到達尾結點的時間就不一致。其實解決這個問題還有一個更簡單的辦法：首先遍歷兩個鏈表得到它們的長度，就能知道哪個鏈表比較長，以及長的鏈表比短的鏈表多幾個結點。在第二次遍歷的時候，在較長的鏈表上先走若干步，接著再同時在兩個鏈表上遍歷，找到的第一個相同的結點就是它們的第一個公共結點。 比如在圖5.3的兩個鏈表中，我們可以先遍歷一次得到它們的長度分別為5和4，也就是較長的鏈表與較短的鏈表相比多一個結點。第二次先在長的鏈表上走1步，到達結點2。接下來分別從結點2和結點4出發同時遍歷兩個結點，直到找到它們第一個相同的結點6，這就是我們想要的結果。 第三種思路和第二種思路相比，時間復雜度都是O（m＋n），但我們不再需要輔助的棧，因此提高了空間效率。當面試官首肯了我們最后一種思路之后，就可以動手寫代碼了。下面是一段參考代碼：  源代碼： 本題完整的源代碼詳見37\_FirstCommonNodesInLists項目。 測試用例： ● 功能測試（輸入的兩個鏈表有公共交點：第一個公共結點在鏈表的中間，第一個公共結點在鏈表的末尾，第一個公共結點是鏈表的頭結點；輸入的兩個鏈表沒有公共結點）。 ● 特殊輸入測試（輸入的鏈表頭結點是NULL指針） 本題考點： ● 考查應聘者對時間復雜度和空間復雜度的理解及分析能力。解決這道題有多種不同的思路。每當應聘者想到一種思路的時候，都要很快分析出這種思路的時間復雜度和空間復雜度是多少，并找到可以優化的地方。 ● 考查應聘者對鏈表的編程能力。 相關題目： 如果把圖5.3逆時針旋轉90°，我們就會發現兩個鏈表的拓撲形狀和一棵樹的形狀非常相似，只是這里的指針是從葉結點指向根結點的。兩個鏈表的第一個公共結點正好就是二叉樹中兩個葉節點的最低公共祖先。在本書7.2節，我們將詳細討論如何求兩個結點的最低公共祖先。 5.4 本章小結 編程面試的時候，面試官通常對時間復雜度和空間復雜度都會有要求，并且一般情況下面試官更加關注時間復雜度。 降低時間復雜度的第一個方法是改用更加高效的算法。比如我們用動態規劃解答面試題31“連續子數組的最大和”能夠把時間復雜度降低到O（n），利用快速排序的Partition函數也能在O（n）時間解決面試題29“數組中出現次數超過一半的數字”和面試題30“最小的k個數字”。 降低時間復雜度的第二個方法是用空間換取時間。在解決面試題35“第一個只出現一次的字符”的時候，我們用數組實現一個簡單的哈希表，于是用O（1）時間就能知道任意字符出現的次數。這種思路可以解決很多同類型的題目。另外，我們可以創建一個緩存保存中間的計算結果，從而避免重復的計算。面試題34“丑數”就是這方面的一個例子。在用遞歸的思路求解問題的時候，如果有重復的子問題，同樣我們也可以通過保存求解子問題的結果來避免重復計算。更多關于遞歸的討論請參考本書的2.4.2節及面試題9“斐波那契數列”。 值得注意的是，以空間換取時間并不一定都是可行的方案。我們要注意需要的輔助空間的大小，消耗太多的內存可能得不償失。另外，我們還要關注問題的背景。如果面試題是有關嵌入式開發的，那對空間消耗就要格外留心，因為通常嵌入式系統的內存很有限。