我在面試中遇到了這個問題，但無法確定比 O(n^2) 更好的解決方案：
將串列元素的“上級”定義為另一個在后且嚴格更大的元素。
撰寫一個函式，該函式接受一個數字串列，并回傳輸入串列中每個元素的上級人數。
示例：[1, 3, 5, 2, 3, 6] -> [5, 2, 1, 2, 1, 0]
有哪些方法可以用來解決 O(n) 時間復雜度的這個問題？
uj5u.com熱心網友回復：
在最壞的情況下O(n log n)，這不能比 更快地完成，因為您可以通過運行兩次來對數字串列進行排序。如果您知道較晚且嚴格更大的元素數量，則可以反轉串列并對較早且嚴格更大的元素再次運行該演算法，之后您只需根據其排名放置每個元素。
對于O(n log n)解決方案，任何可以修改以支持訂單統計的排序集合都可以使用，例如平衡二叉搜索樹。您還可以使用二叉索引樹以更少的代碼實作這一點。
- 制作串列 L 的排序副本，以便您知道每個元素的排名（即它們在排序串列中的索引）。
- 制作一個與 L 長度相同的二叉索引樹來跟蹤我們看到的數字。基礎陣列 A 最初全為零，但在看到第 i 個排序元素后，我們將 A[i] 設定為 1
- 迭代原始串列 L。在迭代 i 時，L[i] 的上級數是索引 i 之后大于 L[i] 的元素數。前綴 sum of
A[0..rank(L[i])]告訴您前面較小的元素數，因此rank(L[i])減去該 sum 告訴您后面較小的元素數，我們通過減去 |L|-i 從中得到上級。 - 更新二叉索引樹，就像我們設定
A[rank(L[i])]為 1 一樣。
轉載請註明出處，本文鏈接：https://www.uj5u.com/qukuanlian/359119.html
標籤：算法
上一篇：是鏈表回文嗎？與指向混淆