Relative Ranks-K6K4.com

原题： https://leetcode.com/problems/relative-ranks/description/
题意： 给定N名运动员的得分，输出他们的名次。前三名分别输出“金奖”，“银奖”，“铜奖”。
约定：（1）N是正整数并且不超过10000；（2）所有运动员的得分是唯一的。
例子：

Input: [5, 4, 3, 2, 1]
Output: ["Gold Medal", "Silver Medal", "Bronze Medal", "4", "5"]
Explanation: The first three athletes got the top three highest scores, so they got "Gold Medal", "Silver Medal" and "Bronze Medal". 
For the left two athletes, you just need to output their relative ranks according to their scores.

标签： medal、ranks、relative、gold、bronze、面试

猜你感兴趣的圈子：

LeetCode交流圈

SLPH

2017-08-11 10:40:16 1楼#1层

Python：

class Solution(object):
    def findRelativeRanks(self, nums):
        """
        :type nums: List[int]
        :rtype: List[str]
        """
        dmap = {v : k for k, v in enumerate(sorted(nums, reverse=True))}
        return [str(dmap[n] + 1) \
               if dmap[n] > 2 \
               else ['Gold', 'Silver', 'Bronze'][dmap[n]] + ' Medal' for n in nums]

SLPH

2017-08-11 10:40:47 2楼#1层

C++解法一：

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        int n = nums.size(), cnt = 1;
        vector<string> res(n, "");
        priority_queue<pair<int, int>> q;
        for (int i = 0; i < n; ++i) {
            q.push({nums[i], i});
        }
        for (int i = 0; i < n; ++i) {
            int idx = q.top().second; q.pop();
            if (cnt == 1) res[idx] = "Gold Medal";
            else if (cnt == 2) res[idx] = "Silver Medal";
            else if (cnt == 3) res[idx] = "Bronze Medal";
            else res[idx] = to_string(cnt);
            ++cnt; 
        }
        return res;
    }
};

SLPH

2017-08-11 10:41:09 3楼#1层

C++解法二：

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        int n = nums.size(), cnt = 1;
        vector<string> res(n, "");
        map<int, int> m;
        for (int i = 0; i < n; ++i) {
            m[nums[i]] = i;
        }
        for (auto it = m.rbegin(); it != m.rend(); ++it) {
            if (cnt == 1) res[it->second] = "Gold Medal";
            else if (cnt == 2) res[it->second] = "Silver Medal";
            else if (cnt == 3) res[it->second] = "Bronze Medal";
            else res[it->second] = to_string(cnt);
            ++cnt;
        }
        return res;
    }
};

SLPH

2017-08-11 10:41:30 4楼#1层

C++解法三：

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        int n = nums.size();
        vector<int> idx(n);
        vector<string> res(n, "");
        for (int i = 0; i < n; ++i) idx[i] = i;
        sort(idx.begin(), idx.end(), [&](int a, int b){return nums[a] > nums[b];});
        for (int i = 0; i < n; ++i) {
            if (i == 0) res[idx[i]] = "Gold Medal";
            else if (i == 1) res[idx[i]] = "Silver Medal";
            else if (i == 2) res[idx[i]] = "Bronze Medal";
            else res[idx[i]] = to_string(i + 1);
        }
        return res;
    }
};

取消

回复

推荐圈子

LeetCode交流圈