RelativeRanks [source code]

public class RelativeRanks {
    public String[] findRelativeRanks(int[] nums) {
        int n = nums.length;
        int[] sorted = Arrays.copyOf(nums, n);
        Arrays.sort(sorted);
        String[] res = new String[n];
        for (int i = 0; i < n; i++) {
            int head = 0, tail = n - 1, mid = (head + tail) / 2;
            while (head <= tail) {
                mid = head + (tail - head) / 2;
                if (nums[i] == sorted[mid]) break;
                else if (nums[i] < sorted[mid]) tail = mid - 1;
                else if (nums[i] > sorted[mid]) head = mid + 1;
            }
            if (mid == n - 1) {
                res[i] = "Gold Medal";
            } else if (mid == n - 2) {
                res[i] = "Silver Medal";
            } else if (mid == n - 3) {
                res[i] = "Bronze Medal";
            } else res[i] = "" + (n - mid);
        }
        return res;
    }
}

这个算法思路总体来说还是还是很简单的; 讲一讲设计的时候的思考方式;
首先, 这种问题第一感觉肯定是希望能够找到一个1pass 的算法, 直接过一遍就所有的结果都有了. 那么这样的一个算法, 要么就是用 stream 算法的思路, 要么就是作为一个 entirety 来思考, 比如这里, 就是先 sort 一遍然后再来做, 这个思路前面有一题的时候已经介绍过一次了;

当然就算不能一个简单的1pass 过完, 你也是希望能够做一个最快的算法的, 这个时候你设计的时候肯定要考虑time. 一个 sort 首先是 nlogn 了, 然后后面的查找是多少呢? 刚开始最直观的想法肯定是n^2, 但是你再想想? 我们这里查找的基础是一个 sorted, 这个前面已经说过了, 2pointers, more specifically, binary search. 这样整个算法的速度就是 nlgn, 这个是可以让人接受的.

讲一些小细节:
binary search内部代码写的时候, 关于 mid 的更新:

                mid = (head + tail) / 2;

这个其实不是特别好, 更好的办法应该是mid = head + (tail - head) / 2, 这样的话 head 本身就不会受到 truncation 的影响; 另外 header 里面是可以取等号的; 以及, 如果 key 肯定在 array 里面的话, 这样的写法最后的结果肯定是mid正好指向 key, 所以 mid 无论如何就是正确的结果; 完整的, 假如考虑key unfound的情况, 那么是要加一个类似return -1这样的处理的. 具体的代码可以看 sedgwick;

另外, 这里在最后得到 mid 之后的处理, 本来的想法是用 switch 来做, 不过查了一下, 基本不可能, JAVA 的 switch 功能很有限, case 1 : ...这里的1, 一定要是一个 constant, 我这里用n - 1这样的一个 locally final的 value 都不接受. 那么这样一来就没什么用了. 直接用 ifelse 来做算了;

另外讨论一个关于 array 复制的问题. 一开始我是这样做的:

int n = nums.length;  
int[] sorted = nums;  
Arrays.sort(sorted);

结果这样当 sorted 被 sort 之后, nums 居然也自动被 sort 了. 也就是说用等号直接完成的复制其实是一个浅复制; 查了一下, 如果想要深复制, 可以用的方法有:

        int[] x = {1, 2, 3, 4, 5};  
        int[] y = x.clone();  

        String[] x = {"one", "two", "three", "four", "five"};  
        String[] y = Arrays.copyOf(x, x.length);  
        String[] z = Arrays.copyOf(x, 3); //will copy the 3 first elements of array x  

        String[] x = {"one", "two", "three", "four", "five"};  
        String[] y = Arrays.copyOfRange(x, 0, x.length); //full copy of the array  
        String[] z = Arrays.copyOfRange(x, x.length-2, x.length); //copy only the last 2 elements

注意这里copyOfRange的 arg3不太好理解, 如果用endIndex的思路来理解, 要记住这个 endIndex 是不被包含的;

速度是19ms, 81%, 可以接受;

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