-3

I need an O(n log n) algorithm to remove repeated elements from a list. I know that I can use a set, for example but I need an algorithm of this specific complexity and I have no idea how to code it. Since I now have this code, but I don't know what is its complexity although I believe it is not n log n.

def removing(a):

for e in a:
    if e in a[a.index(e)+1:]:
        a.remove(e)

return a

The exercise says it wants an O(n*log(n)) algorithm, and says nothing about sorting the list before.

Michael Foukarakis
  • 39,737
  • 6
  • 87
  • 123
arnaugamez
  • 23
  • 7
  • In one of the comments below, you have mentioned that "Yes, I know I can use list(set(a)), but what the exercice says is that it wants an n*log n algorithm, and says nothing about sorting the list before". Expecting answers for a homework question is discouraged here. However a hint - log N requires a divide and conquer approach. Use partitioning seen in quicksort. – Sriram Nov 25 '14 at 11:00
  • If you don't know what complexity it has, I suggest you try it. Give it an "a" list with 10 members, 100 members, 1000 members, 10000 members. Do a plot of the time it takes to compute it (https://docs.python.org/2/library/timeit.html) vs the number of elements and look if it has the correct shape (http://stackoverflow.com/questions/7830727/n-log-n-is-on) – Jblasco Nov 25 '14 at 11:54
  • It's a little subproblem from a very long list of exercices to practice. I get stucked, probably because I do not know well how works complexity. Thanks for you answers – arnaugamez Nov 25 '14 at 20:37

2 Answers2

0

Since it's an assignment, I'll just hint you - you can use the set solution, and have a O(nlogn) worst case performance by using an OrderedDict instead of a regular set (the mappings of the keys do not matter, you can map them all to None, or some other arbitrary value)

If the order of the elements in the resulting list does not matter, simplest solution would be to just sort, and then iterate, and exclude elements such that a[i] == a[i+1]. The result will be a sorted list with all unique elements, and is done in O(nlogn)

Good Luck.

amit
  • 175,853
  • 27
  • 231
  • 333
-1
x=[1,2,3,4,6,6,2,3,1]

dic={}
for i in x:
    dic[i]=0

print dic.keys()

You can try this.

vks
  • 67,027
  • 10
  • 91
  • 124
  • (1) You should avoid giving complete "ready to use" answers to homework questions. (expected 10k+ rep users will be aware of it) (2) it does not meet the complexity requirements for worst case performance. The OP clearly gave this solution in the question itself, and said it doesn't meet the requirements. – amit Nov 25 '14 at 11:01
  • @amit OP's solution is not same.Also this is within `nlogn`. – vks Nov 25 '14 at 11:04
  • 1
    @amit https://meta.stackexchange.com/questions/10811/how-do-i-ask-and-answer-homework-questions - 'Don't downvote others who answer homework questions in good faith, even if they break these guidelines' – Squidly Nov 25 '14 at 11:05
  • 1
    @MrBones I downvoted because of (1) and (2), and (2) on its own deserves a downvote, as it is clearly not what the OP is looking for - as he **explicitly stated this exact solution in the question itself**. – amit Nov 25 '14 at 11:06