web算法中數(shù)據(jù)結(jié)構(gòu)的技巧有哪些

這篇文章主要講解了“web算法中數(shù)據(jù)結(jié)構(gòu)的技巧有哪些”，文中的講解內(nèi)容簡(jiǎn)單清晰，易于學(xué)習(xí)與理解，下面請(qǐng)大家跟著小編的思路慢慢深入，一起來(lái)研究和學(xué)習(xí)“web算法中數(shù)據(jù)結(jié)構(gòu)的技巧有哪些”吧！

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

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

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

當(dāng)以“查找列表中第K個(gè)最小元素”的形式提出問(wèn)題時(shí)，由于問(wèn)題語(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è)最小的問(wèn)題使用最大堆。

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

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

技巧2：使用索引映射

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

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

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

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

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

想找到給定節(jié)點(diǎn)的下標(biāo)，比如說(shuō)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)的索引。無(wú)論何時(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)，例如索引映射的樹(shù)。

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

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

問(wèn)題：在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。

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

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

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

問(wèn)題：

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

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

技巧5：位操作

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

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

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

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

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

你當(dāng)然可以使用哈希表或其他技術(shù)來(lái)解決這個(gè)問(wèn)題，但我有一個(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)存。

感謝各位的閱讀，以上就是“web算法中數(shù)據(jù)結(jié)構(gòu)的技巧有哪些”的內(nèi)容了，經(jīng)過(guò)本文的學(xué)習(xí)后，相信大家對(duì)web算法中數(shù)據(jù)結(jié)構(gòu)的技巧有哪些這一問(wèn)題有了更深刻的體會(huì)，具體使用情況還需要大家實(shí)踐驗(yàn)證。這里是億速云，小編將為大家推送更多相關(guān)知識(shí)點(diǎn)的文章，歡迎關(guān)注！