每個元素列表中出現的次數

Question

給定一個列表[x_1，x_2，...，x_n]。我正在尋找一個有效的函數實現，它將一個列表作爲輸入並輸出一個類型爲[（x_1'，n_1），...，（x_m'，n_m）]的列表，其中x_i'都是distinct並且n_i表示輸入列表中x_i'的出現次數。

在沒有突變的二次時間內做這件事很簡單。然而，在命令式語言中，一個典型的簡單方法是使用一個數組並在每個列表元素上使用數組[x_i] ++，然後掃描該數組以獲得非零的條目，並使用它構建輸出列表。運行時間是線性的（對於非常小的輸入，性能很差）。

有一個明顯更好的實現沒有突變。如果x_i具有明確定義的順序，則可以構造二叉搜索樹。在樹中查找（x_i，k）。如果它不在樹中插入（x_i，1），否則從樹中刪除（x_i，k）並插入（x_i，k + 1）。最後，遍歷將其轉換爲列表的樹。或者，對列表進行排序，然後以線性時間遍歷它。兩者都是O（nlog（n））。

有沒有更好的算法沒有突變？

Answer 1

考慮以下問題：給定可比較值的一般列表，確定是否所有元素都是唯一的。

假設您所知道的所有值都是比較操作，您可以使用sorting lower bound proof來顯示此算法需要O（n log n）個步驟。由於你的問題解決了比這個問題更強的問題，所以它也具有O（n log n）作爲下限。