Leetcode: Relative Ranks

Relative Ranks

Given an integer array of size n, find all elements that appear more than n/3 times. The algorithm should run in linear time and in O(1) space.

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.

## Blog link: https://code.dennyzhang.com/relative-ranks
## Basic Ideas:
##           Sort the list. Build a map. key(score): value(position in sorted list)
##           Trasverse the original list again, get the position by map
## Complexity: Time O(n*log(n)), Space O(n)
class Solution(object):
    def findRelativeRanks(self, nums):
        :type nums: List[int]
        :rtype: List[str]
        score_nums = sorted(nums)
        m = {}
        for i in xrange(len(score_nums)):
            m[score_nums[i]] = i

        res = []
        for num in nums:
            rank = m[num]
            if rank == 0: element = 'Gold Medal'
            elif rank == 1: element = 'Silver Medal'
            elif rank == 2: element = 'Bronze Medal'
            else: element = str(rank+1)
        return res

Share It, If You Like It.

Leave a Reply

Your email address will not be published.