CODEWITHSUNDEEP
arraysalgorithm
Vercryger
Vercryger

Reputation: 620

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

Lets say we have an array of n numbers: a = [4,8,2,7,7], so i need the the "same array", but with no repeated items, so one idea would be, take the a[n-1] and make a comparison with the a[n-2], if a[n-2] = a[n-1], then a[n-2] += 1, and repeat this process n-1 times until get the array with no repeated items, but in general if a[n] > a[n+1] the resulted array must keep this order, idem if a[n] < a[n+1]. But there is a problem with this, what about if the array was a = [6,6,2,8,7], the last comparison would result a = [7,6,2,8,7] and now a[0] = a[n-1].

There is a better option to do this? Ideas?

Upvotes: 0

Views: 44

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Here's a straightforward O(n log n)-time algorithm. Prepare a list p = [0,...,n-1] and sort it stably by indexing into a to determine the results of the comparisons, e.g., for a = [4,8,2,7,7], the sorted list is p = [2,0,3,4,1], and for a = [6,6,2,8,7], the sorted list is p = [2,0,1,4,3]. Compute the inverse permutation, i.e., define another array q such that q[p[i]] = i for all i = 0,...,n-1. Iterate i = 1,...,n-1, setting a[q[i]] = max(a[q[i]], a[q[i-1]]+1).

Upvotes: 1

Related Questions