如何從數組中抑制重複的項目但保持順序？

Question

比方說我們有n數字數組：a = [4,8,2,7,7]，所以我需要的「同一陣列」，但沒有重複的項目，所以一個想法是，採取a[n-1]，並與a[n-2]比較，如果a[n-2] = a[n-1]，然後a[n-2] + = 1，並重復這一過程n-1次，直到得到沒有重複項陣列，但一般如果a[n]>a[n+1]所得到的陣列必須保持這個順序，同上如果a[n] < a[n+1]。 但是，這有一個問題，如果數組是a = [6,6,2,8,7]，最後的比較會導致a = [7,6,2,8,7]，現在a[0] = a[n-1]。

有更好的選擇來做到這一點？想法？

Answer 1

這是一個簡單的O（n log n）時間算法。準備清單p = [0,...,n-1]並通過索引到a以確定比較的結果，例如a = [4,8,2,7,7]，排序的清單是p = [2,0,3,4,1]，並且對於a = [6,6,2,8,7]，排序的清單是p = [2,0,1,4,3]，將其穩定地排序。計算逆置換，即，定義另一個陣列q，使得所有i = 0,...,n-1的q[p[i]] = i。迭代i = 1,...,n-1，設置a[q[i]] = max(a[q[i]], a[q[i-1]]+1)。