RelativeRanksOPT [source code]

public class RelativeRanksOPT {
    public String[] findRelativeRanks(int[] nums) {
        String[] result = new String[nums.length];
        int max = 0;
        for (int i : nums) {
            if (i > max) max = i;
        }
        int[] hash = new int[max + 1];
        for (int i = 0; i < nums.length; i++) {
            hash[nums[i]] = i + 1;
        }
        int place = 1;
        for (int i = hash.length - 1; i >= 0; i--) {
            if (hash[i] != 0) {
                if (place == 1) {
                    result[hash[i] - 1] = "Gold Medal";
                } else if (place == 2) {
                    result[hash[i] - 1] = "Silver Medal";
                } else if (place == 3) {
                    result[hash[i] - 1] = "Bronze Medal";
                } else {
                    result[hash[i] - 1] = String.valueOf(place);
                }
                place++;
            }
        }
        return result;
    }
}

这个是 submission 最优解, 8ms, 99%;

总体的思路还是比较清晰的, 就是利用一个value as index的思路, 来完成一个counting sort; 过程中用一个类似 end 的 pointer 来保存当前的赋值进度;
这个算法基本完成了我本来想要完成的任务, 就是一个1pass 就结束. 整个算法的速度应该是 linear 的; 这里他稍微一个小技巧, 就是hash array的 size 只控制到 max, 不然控制到 domain 的最大值就没有必要了, 而且增加最后一个 loop 的时间;

另外他这里的i + 1其实没有什么特别的用处, 后面又减掉了;

好像他们常说的 hash 就是我这里的value as index的意思? 实质上, 这两个操作都是把一个现成的 array 放到另外一个 array 里面; 如果回忆之前看书的时候, 好像 hashing 的意思就是全部放到一个大 array 里面的意思;

题外话, 比如下面这个循环:

for (int i = 0; i < nums.length; i++) {  
    hash[nums[i]] = i + 1;  
}

假如看不懂, 一个最 mechanical 的方法就是:

1. 读header, 知道loop var是什么, 这里是 i; 知道这个 i 的范围, 比如这里是0..n-1;
2. 脑子里这样告诉自己: 在 body 里面先找到 i 的位置, 然后说, "我知道了这个 i", 然后向外层扩散, 看这个 i 被用来干什么, 这里我们下一步是"我知道了 nums[i]"; 然后这个被用来作为 hash 的 index. 右边的 value 则是i + 1. 这样首先知道了干的是什么, 至于具体是什么意思, 这个时候应该好理解很多了;

Problem Description

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:
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.
Difficulty:Easy
Category:Algorithms
Acceptance:46.78%
Contributor: taylorty10
Companines
Google