Efficient algorithm to found duplicated values

Asked Mar 18 '21 at 18:49

Active Mar 18 '21 at 18:49

Viewed 30 times

I'm practice some algorithms lessons at Codility, and i'm now at that lesson

To resolve that, I created the algorithm as follow:

A = [9,3,9,3,9,7,9]
for index, item in enumerate(A):
    counter = A.count(item)
    if(counter == 1):
        output = item
        print(output)

The algorithm works as well, but he is not performatic... I get just 25% of efficient and I will appreciate opinions about how can I make that code better?

I guess that he count each index can make it not-performatic... any suggestion to improve that?

Thank you!

asked Mar 18 '21 at 18:49

LuizGTVSilva

2

Use `collections.Counter()`. – Barmar Mar 18 '21 at 18:52
Why are you using `enumerate` here? Note that `index` isn't used in the body of the loop. The problem with you code is that `A.count(item)` sweeps over the whole list for each item, making your algorithm quadratic in complexity. The suggestion of @Barmar will get it down to linear. – John Coleman Mar 18 '21 at 18:54
@Barmar did you have any example to show me? – LuizGTVSilva Mar 18 '21 at 19:06
Did you read the linked question? It has 36 examples. – Barmar Mar 18 '21 at 19:06
@JohnColeman yeah I get it... thanks a lot :) – LuizGTVSilva Mar 18 '21 at 19:06
@Barmar ? yes of course I did... – LuizGTVSilva Mar 18 '21 at 19:07
1

Then what's the problem? I'm not going to repeat the examples here. – Barmar Mar 18 '21 at 19:08
@Barmar sorry, I thought you are talking about the lesson of codility, not the stackoverflow link ;) my bad, I will take a look, and thank you for your attention – LuizGTVSilva Mar 18 '21 at 19:10

Efficient algorithm to found duplicated values

0 Answers0