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.

Solution

Sort & Binary search, time O(nlogn), space O(n)

感觉应该有更优的解法。。

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        int[] ranks = nums.clone();
        Arrays.sort(ranks);
        int n = nums.length;
        String[] res = new String[n];
        
        for (int i = 0; i < n; ++i) {
            int index = binarySearch(ranks, nums[i]);
            if (index == n - 1) {
                res[i] = "Gold Medal";
            } else if (index == n - 2) {
                res[i] = "Silver Medal";
            } else if (index == n - 3) {
                res[i] = "Bronze Medal";
            } else {
                res[i] = String.valueOf(n - index);
            }
        }
        
        return res;
    }
    
    public int binarySearch(int[] a, int v) {
        int left = 0;
        int right = a.length;
        
        while (left + 1 < right) {
            int mid = left / 2 + right / 2;
            if (a[mid] < v) {
                left = mid + 1;
            } else if (a[mid] > v) {
                right = mid;
            } else {
                return mid;
            }
        }
        
        return left;
    }
}

MaxHeap, O(n log n), S(n)

class Solution {
    public String[] findRelativeRanks(int[] nums) {
        PriorityQueue<int[]> queue = new PriorityQueue<>((a, b) -> b[1] - a[1]);
        for (int i = 0; i < nums.length; ++i) {
            queue.offer(new int[] {i, nums[i]});
        }
        
        String[] res = new String[nums.length];
        int rank = 1;
        while (!queue.isEmpty()) {
            int[] arr = queue.poll();
            int index = arr[0];
            
            switch (rank) {
                case 1:
                    res[index] = "Gold Medal";
                    break;
                case 2:
                    res[index] = "Silver Medal";
                    break;
                case 3:
                    res[index] = "Bronze Medal";
                    break;
                default:
                    res[index] = Integer.toString(rank);
            }
            
            ++rank;
        }
        
        return res;
    }
}