Use a dictionary mapping scores to ranks.
def findRelativeRanks(self, nums):
sort = sorted(nums)[::-1]
rank = ["Gold Medal", "Silver Medal", "Bronze Medal"] + map(str, range(4, len(nums) + 1))
return map(dict(zip(sort, rank)).get, nums)
@StefanPochmann
This has nothing to do with the problem, but what is the time complexity of reversing a list using [::-1]
? I see it used a lot in Python but wonder if it's as fast as using the reverse
parameter in sorted
. Isn't using the list slice technically adding another whole iteration through the list?
@david120 Do you have any reason to believe it might be something other than Θ(n)?
Which then doesn't change the complexity, as the sorting already takes O(n log n) average and worst case, and Θ(n) best case. And that best case has to look at all values and compare neighbors to see that the list is already sorted. Reversing a list doesn't, so that's a faster Θ(n). I ran some tests on a shuffled list with a million entries, comparing sorted(a)
, sorted(a, reverse=True)
and sorted(a)[::-1]
:
sort rev=T [::-1]
4.38 4.38 4.44
4.38 4.59 4.75
4.74 4.72 4.58
4.40 4.41 4.44
4.41 4.49 4.46
Not much of a difference. And here are test results for the list already sorted, so best case for the sorting part:
sort rev=T [::-1]
0.16 0.16 0.21
0.15 0.16 0.20
0.19 0.17 0.19
0.21 0.16 0.20
0.16 0.18 0.21
The code (for my second test I took out the shuffling):
from timeit import timeit
import random
a = range(10**6)
print 'sort rev=T [::-1]'
for _ in range(5):
random.shuffle(a)
print '%.2f %.2f %.2f' % (timeit(lambda: sorted(a), number=10),
timeit(lambda: sorted(a, reverse=True), number=10),
timeit(lambda: sorted(a)[::-1], number=10))
Maybe I should use the reverse
parameter instead. But [::-1]
is less to type :-P
Though five of its six characters involve the poor right pinky, so that's not good...
@StefanPochmann Fun fact: During my above tests I noticed something unexpected and turned it into a nice StackOverflow question ("Why is copying a shuffled list much slower?"). So thanks for that, David :-)
@StefanPochmann
Nice tests. No I had no reason to believe that the list slice would have anything other than linear time complexity. I just thought sorted
with reverse=True
might be faster because it just internally reverses the cmp
parameter. This way, sorted
essentially builds the result in an already reversed configuration ( O(n log n) ), while the list slice takes the sorted result and has to run through each element one more time ( O(n log n) + Θ(n), which I admit is still O(n log n) ).
Very interesting post regarding the copying of a shuffled list though. I've never seen memory locality actually come into play like this.
@david120 said in Python solution:
I just thought
sorted
withreverse=True
might be faster because it just internally reverses thecmp
parameter.
Actually... I think it would be costly to have that overhead for every comparison. So I had a quick look and if I'm not mistaken, what reverse=True
does is it causes the algorithm to reverse the data before the sorting and to reverse it again after the sorting. So that's two reversals compared to my one reversal.