algorithm - How to supress repeated items from an array but keeping the order? -

algorithm - How to supress repeated items from an array but keeping the order? -

lets have array of n numbers: a = [4,8,2,7,7], need the "same array", no repeated items, 1 thought be, take a[n-1] , create comparing a[n-2], if a[n-2] = a[n-1], a[n-2] += 1, , repeat process n-1 times until array no repeated items, in general if a[n] > a[n+1] resulted array must maintain order, idem if a[n] < a[n+1]. there problem this, if array a = [6,6,2,8,7], lastly comparing result a = [7,6,2,8,7] , a[0] = a[n-1].

there improve alternative this? ideas?

here's straightforward o(n log n)-time algorithm. prepare list p = [0,...,n-1] , sort stably indexing a determine results of comparisons, e.g., a = [4,8,2,7,7], sorted list p = [2,0,3,4,1], , a = [6,6,2,8,7], sorted list p = [2,0,1,4,3]. compute inverse permutation, i.e., define array q such q[p[i]] = i i = 0,...,n-1. iterate i = 1,...,n-1, setting a[q[i]] = max(a[q[i]], a[q[i-1]]+1).

arrays algorithm