("Distinctify" may be semantically better, but doesn't sound right)

Here's a challenge: Given a list in L1, output in L2 the list with all distinct elements, whose elements are in order of their first occurrence in L1. For example, {3,1,4,1,5,9,2,6,5,3,5} becomes {3,1,4,5,9,2,6}. Do this as fast as possible. I'll be measuring any programs I write on 2.55MP.

L1 will have exactly 256 elements, all of which are integers in [1,10^6]. The distribution of L1 will be such that there are about 128 total repetitions. The generation algorithm for L1 is the following:

* Generate one random number in [1,10^6]
* Repeat the following 255 times:
* With probability 1/2, generate a number in [1,10^6] different from all numbers already in the list.
* Otherwise, pick a random number from the unique numbers in the list so far. That is, if the list so far is {6,6,6,4}, a 4 is as likely to be picked as a 6 for the next element.
* Append that number to the list.

* Finally, shuffle the list.

You will not need to generate L1, only uniquify it placing the result in L2. Other average numbers of duplicates (or an in-place uniquify algorithm) may also be interesting, but let's try this one first.
Here's what I have thus far:

If min(L2!=Ans

This would probably work as a generating algorithm:

ClrList L2
Note that this is pretty similar to RLE.
It is, but I'm hoping that an O(n) or O(n log n) approach will prevail here over the O(n^2) you solved RLE with.
Both can be done in O(n), if you have efficient compaction.
Register to Join the Conversation
Have your own thoughts to add to this or any other topic? Want to ask a question, offer a suggestion, share your own programs and projects, upload a file to the file archives, get help with calculator and computer programming, or simply chat with like-minded coders and tech and calculator enthusiasts via the site-wide AJAX SAX widget? Registration for a free Cemetech account only takes a minute.

» Go to Registration page
Page 1 of 1
» All times are UTC - 5 Hours
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum