web算法中數據結構的技巧有哪些

這篇文章主要講解了“web算法中數據結構的技巧有哪些”，文中的講解內容簡單清晰，易于學習與理解，下面請大家跟著小編的思路慢慢深入，一起來研究和學習“web算法中數據結構的技巧有哪些”吧！

技巧1：針對“第K個最小/最大元素”問題的最小/最大堆

問題:給定一個數字列表，使用堆數據結構找到第三小的元素：

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

當以“查找列表中第K個最小元素”的形式提出問題時，由于問題語句中的“最小”一詞，自然會傾向于使用最小堆提出解決方案。這兒有一個簡單的解決方案：

構建給定列表的最小堆并調用extractMin() k次。這個解決方案的時間復雜度是O(n + kLogn)，消耗了O(n)的額外內存。

想要優化內存和時間復雜度，這兒有一個更好的解決方案：

• 從數組的前k個元素構建最大堆

• 對于每個剩余的元素，將該元素與最大堆的根進行比較。如果它小于根，則用元素替換根并調用heapify()。

• 完成了第二步，堆的根將是第k個最小的元素。

時間復雜度:O(k +(n-k)Logk)

• 對于第K個最小的問題使用最大堆。

• 對于第K個最大的問題使用最小堆。

注意:對于這個問題有不同的解決方案，可以使用快速選擇算法、中位數等。選擇堆是因為它們更容易理解和可視化。

技巧2：使用索引映射

索引映射是在技術面試中多次使用的一種技術，它以使用更多內存為代價來節省搜索時間。

問題:用O(1)搜索時間實現最小堆數據結構。

從簡單開始。只關注“搜索”部分，最小堆已經實現了。

這是一個最小堆，它被表示為如下數組：

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

想找到給定節點的下標，比如說10。

對數組進行線性搜索，直到找到元素10，這將花費O(n)時間。但需要O(1)時間。也許是因為想要更新這個節點的值，正在執行大量的更新，所以不想花時間去尋找元素。

很明顯，除非犧牲一些資源，否則不可能神奇地擁有O(1)搜索時間。我們可以在哈希映射中保留每個節點的索引。無論何時更新堆，都需要更新這個散列映射上的索引。

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

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

現在我們可以求出節點10在O(1)時間內的位置。如果更改堆中元素的順序，還將更新它們在索引映射數據結構中的相對索引。

注意:可以使用其他的數據結構，例如索引映射的樹。

追問:能對指針/引用使用同樣的技術嗎?

技巧3：在O(1)時間內從無序數組中刪除一個元素

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

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

但如果你不在意元素的順序，有一個更簡單的方法可以實現O(1)時間內“刪除”：用數組的最后一個元素替換要刪除的元素。然后將數組大小減小1。

對于上面這個例子，刪除“4”就可以寫成：

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

追問：如果在意順序呢?可以將其保存在不同的數據結構中嗎?

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

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

問題：

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

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

技巧5：位操作

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

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

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

問題:給定一個整數數組，除了一個元素外，其他元素都出現兩次。找到這個元素。

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

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

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

這將只花費O(n)時間和O(1)內存。

感謝各位的閱讀，以上就是“web算法中數據結構的技巧有哪些”的內容了，經過本文的學習后，相信大家對web算法中數據結構的技巧有哪些這一問題有了更深刻的體會，具體使用情況還需要大家實踐驗證。這里是億速云，小編將為大家推送更多相關知識點的文章，歡迎關注！