leetcode解题: Relative Ranks (506)

发表于 | 分类于

Given scores of N athletes, find their relative ranks and the people with the top three highest scores, who will be awarded medals: “Gold Medal”, “Silver Medal” and “Bronze Medal”.

Example 1:

1
2
3
4
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.

Note:
N is a positive integer and won’t exceed 10,000.
All the scores of athletes are guaranteed to be unique.

解法1：Priority Queue

这里感觉是要用一个带下标的排序，那么我们可以自己实现一个带下标的排序，或者可以使用已有的可排序的数据结构。对于可排序的比较熟悉的就是PriorityQueue了。
每一个放入的元素都会自动排序，那么我们只需要全部放入然后一个个读出同时判断是第几个元素就可以解决medal的归属问题。
用一个辅助class记录data和index，同时实现一个comparator，来比较这两个pair。

Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
class pair {
    int data;
    int index;
    public pair(int d, int i) {
        this.data = d;
        this.index = i;
    }
};
public class Solution {
    public String[] findRelativeRanks(int[] nums) {
        Comparator<pair> comparator = new Comparator<pair>() {
            public int compare(pair a, pair b) {
                if (a.data < b.data) {
                    return -1;
                } else if (a.data == b.data) {
                    return 0;
                } else {
                    return 1;
                }
            }
        };
        PriorityQueue<pair> queue = new PriorityQueue<pair>(nums.length, comparator);
        for (int i = 0; i < nums.length; ++i) {
            queue.offer(new pair(nums[i], i));
        }
        
        String[] res = new String[nums.length];
        for (int i = 0; i < nums.length; ++i) {
            pair temp = queue.peek();
            if (queue.size() > 3) {
                res[temp.index] = Integer.toString(queue.size());
            } else if (queue.size() == 3) {
                res[temp.index] = "Bronze Medal";
            } else if (queue.size() == 2) {
                res[temp.index] = "Silver Medal";
            } else {
                res[temp.index] = "Gold Medal";
            }
            queue.poll();
        }
        return res;
    }
}