Python solution

  • 19

    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)

  • 3

    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?

  • 1

    @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):
        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...

  • 3

    @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 :-)

  • 0

    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.

  • 0

    Thanks a lot! It is very neat!

  • 0

    @david120 said in Python solution:

    I just thought sorted with reverse=True might be faster because it just internally reverses the cmp 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.

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.