My 12ms O(n) solution in java

  • 0

    Borrow the idea of Pigeonhole Sort, since the scores are UNIQUE, we can use a int[] array as a hash map map[] to store the score-index info. Then we traverse the array map[] in the descent order of scores, it will automatically sort score-index. For each score, we find its index map[i] in original array and assign that position in the original array nums[map[i]] as the ranking number j, which keeps adding 1 whenever it encounters a non-null element.
    Since such sorting is not comparison based, it doesn’t have the O(nlogn) lower bound so it can be faster than most sorting methods.
    TC: O(n+range) SC: O(range) where range is the range of ints in nums[], also it is the length of map[].
    It is my first time to submit my answer, help leave comment if you have any suggestions or better ideas to help improve my post! :)

    public String[] findRelativeRanks(int[] nums) {
            int max = nums[0], min = nums[0];
            for(int i=1, n = nums.length; i<n; i++) {
                max = Math.max(max, nums[i]);
                min = Math.min(min, nums[i]);
            int length = max - min +1;
            Integer[] map = new Integer[length];
            for(int i=0, n = nums.length; i<n; i++) {
                map[max - nums[i]] = i;
            String[] res = new String[nums.length];
            for (int i=0, j=0; i<length; i++){
                if(map[i] == null) continue;
                else {
                    if(j == 0) res[map[i]] = "Gold Medal";
                    else if(j == 1) res[map[i]] = "Silver Medal";
                    else if(j == 2) res[map[i]] = "Bronze Medal";
                    else res[map[i]] = j+1+"";
            return res;

Log in to reply

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.