本文轉(zhuǎn)載自公眾號(hào)“讀芯術(shù)”(ID：AI_Discovery)

如果你即將要面臨大型科技公司的技術(shù)面試，那么數(shù)據(jù)結(jié)構(gòu)和算法技巧方面的問題一定不能忘記準(zhǔn)備。

本文就將介紹一些適合在面試使用的優(yōu)化代碼的小技巧。但在學(xué)習(xí)技巧之前，你得確保自己已經(jīng)了解了簡(jiǎn)單的數(shù)據(jù)結(jié)構(gòu)，比如樹、堆、圖和哈希映射。

注意，你要理解而不是僅僅記住它們。

[[327840]]

技巧1：針對(duì)“第K個(gè)最小/最大元素”問題的最小/最大堆

問題:給定一個(gè)數(shù)字列表，使用堆數(shù)據(jù)結(jié)構(gòu)找到第三小的元素：

[4,20,16,10,0,47，…] 

當(dāng)以“查找列表中第K個(gè)最小元素”的形式提出問題時(shí)，由于問題語(yǔ)句中的“最小”一詞，自然會(huì)傾向于使用最小堆提出解決方案。這兒有一個(gè)簡(jiǎn)單的解決方案：

構(gòu)建給定列表的最小堆并調(diào)用extractMin() k次。這個(gè)解決方案的時(shí)間復(fù)雜度是O(n + kLogn)，消耗了O(n)的額外內(nèi)存。

想要優(yōu)化內(nèi)存和時(shí)間復(fù)雜度，這兒有一個(gè)更好的解決方案：

• 從數(shù)組的前k個(gè)元素構(gòu)建最大堆
• 對(duì)于每個(gè)剩余的元素，將該元素與最大堆的根進(jìn)行比較。如果它小于根，則用元素替換根并調(diào)用heapify()。
• 完成了第二步，堆的根將是第k個(gè)最小的元素。

時(shí)間復(fù)雜度:O(k +(n-k)Logk)

• 對(duì)于第K個(gè)最小的問題使用最大堆。
• 對(duì)于第K個(gè)最大的問題使用最小堆。

注意:對(duì)于這個(gè)問題有不同的解決方案，可以使用快速選擇算法、中位數(shù)等。選擇堆是因?yàn)樗鼈兏菀桌斫夂涂梢暬?/p>

技巧2：使用索引映射

索引映射是在技術(shù)面試中多次使用的一種技術(shù)，它以使用更多內(nèi)存為代價(jià)來節(jié)省搜索時(shí)間。

問題:用O(1)搜索時(shí)間實(shí)現(xiàn)最小堆數(shù)據(jù)結(jié)構(gòu)。

從簡(jiǎn)單開始。只關(guān)注“搜索”部分，最小堆已經(jīng)實(shí)現(xiàn)了。

這是一個(gè)最小堆，它被表示為如下數(shù)組：

[0, 4, 16, 10, 20, 47] 

想找到給定節(jié)點(diǎn)的下標(biāo)，比如說10。

對(duì)數(shù)組進(jìn)行線性搜索，直到找到元素10，這將花費(fèi)O(n)時(shí)間。但需要O(1)時(shí)間。也許是因?yàn)橄胍逻@個(gè)節(jié)點(diǎn)的值，正在執(zhí)行大量的更新，所以不想花時(shí)間去尋找元素。

很明顯，除非犧牲一些資源，否則不可能神奇地?fù)碛蠴(1)搜索時(shí)間。我們可以在哈希映射中保留每個(gè)節(jié)點(diǎn)的索引。無論何時(shí)更新堆，都需要更新這個(gè)散列映射上的索引。

對(duì)于上面的堆[0,4,16,10,20,47]，索引映射為：

{ 
0:0, 
4:1, 
16:2 
10:3, 
20:4 
47:5 
} 

現(xiàn)在我們可以求出節(jié)點(diǎn)10在O(1)時(shí)間內(nèi)的位置。如果更改堆中元素的順序，還將更新它們?cè)谒饕成鋽?shù)據(jù)結(jié)構(gòu)中的相對(duì)索引。

注意:可以使用其他的數(shù)據(jù)結(jié)構(gòu)，例如索引映射的樹。

追問:能對(duì)指針/引用使用同樣的技術(shù)嗎?

技巧3：在O(1)時(shí)間內(nèi)從無序數(shù)組中刪除一個(gè)元素

問題：在O(1)時(shí)間內(nèi)移除[10,4,56,0,8,1]中的元素“4”。

從數(shù)組中刪除一個(gè)特定的元素時(shí)，所有后續(xù)的元素都向左移動(dòng)，這將花費(fèi)O(n)個(gè)時(shí)間。這很完美，而且是最常用的技術(shù)，它保留了數(shù)組的順序。

但如果你不在意元素的順序，有一個(gè)更簡(jiǎn)單的方法可以實(shí)現(xiàn)O(1)時(shí)間內(nèi)“刪除”：用數(shù)組的最后一個(gè)元素替換要?jiǎng)h除的元素。然后將數(shù)組大小減小1。

對(duì)于上面這個(gè)例子，刪除“4”就可以寫成：

[10, 1, 56, 0, 8, 1] #用最后一個(gè)元素“1”替換“4” 
[10, 1, 56, 0, 8] #減少數(shù)組大小1。 

追問：如果在意順序呢?可以將其保存在不同的數(shù)據(jù)結(jié)構(gòu)中嗎?

技巧4：了解二分查找的基本原理

二分查找不僅僅是為了在一個(gè)有序數(shù)組中找到一個(gè)元素，它有著更強(qiáng)大的力量。一旦理解了它的基本原理，就會(huì)被能用它解決的問題的能力所折服。

問題：

農(nóng)民約翰新建了一個(gè)有N個(gè)畜欄的倉(cāng)房。給定一個(gè)大小為N的整數(shù)數(shù)組A，其中數(shù)組中的每個(gè)元素表示畜欄的位置，整數(shù)B表示奶牛的數(shù)量。他的奶牛不喜歡這個(gè)倉(cāng)房的布局，這使它們?cè)趥}(cāng)庫(kù)中變得很有攻擊性。為了防止奶?；ハ鄠Γs翰想把奶牛分配到畜欄里。

[[327842]]

圖源：unsplash

約翰想使它們之間的最小距離盡可能大。那么這個(gè)最小距離的最大值是多少?我們能用二分查找法解決這個(gè)問題嗎?

當(dāng)然可以。閱讀這篇關(guān)于topcoder的文章，你將會(huì)明白該怎樣具體操作：

mailto:https://www.topcoder.com/community/competitive-programming/tutorials/binary-search

技巧5：位操作

位操作是優(yōu)化代碼(主要是內(nèi)存)的一種有用技術(shù)，可以用于各種問題，你可以使用移位、和/或/異或/非操作。

以下是你必須了解的比特操作：

x ^ x = 0 
x ^ 0 = x 
x | 0 = x 
x & 1 = xGet i th bit on num: (num & (1 << i)) != 0 
Set i th bit on num: num |= 1 << i 

問題:給定一個(gè)整數(shù)數(shù)組，除了一個(gè)元素外，其他元素都出現(xiàn)兩次。找到這個(gè)元素。

Sample input: [1, , 8, 1, 8] 
Output: 0 

你當(dāng)然可以使用哈希表或其他技術(shù)來解決這個(gè)問題，但我有一個(gè)更簡(jiǎn)單的方法。我們給到的是x ^ 0 =x和x ^ x =0。如果對(duì)數(shù)組的所有元素進(jìn)行XOR操作，重復(fù)的元素會(huì)相互抵消(x ^ x = 0)，最后，會(huì)得到不重復(fù)的元素：

arr = [1, 0, 8, 1, 8] 
result = 0for num in arr: 
  result ^= numreturn result 

這將只花費(fèi)O(n)時(shí)間和O(1)內(nèi)存。

[[327843]]

圖源：unsplash

技巧的意義體現(xiàn)在實(shí)際操作之中，快去試試用它們解答面試問題吧，你會(huì)大有收獲的。