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)
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, reverse=True) and
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 :-)
Nice tests. No I had no reason to believe that the list slice would have anything other than linear time complexity. I just thought
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.
I just thought
reverse=Truemight be faster because it just internally reverses the
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.
Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.