Java Solution, O(n), TreeMap sorting


  • 1

    class Solution {
    public String[] findRelativeRanks(int[] nums) {
    String[] result = new String[nums.length];
    Map<Integer, Integer> map = new TreeMap<>(Collections.reverseOrder());

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], i);
        }
        
        int index = 1;
        for (Integer value : map.values()) {
            result[value] = String.valueOf(index);
            index++;
        }
        
        for (int i = 0; i < result.length; i++) {
            if (result[i].equals("1")) {
                result[i] = "Gold Medal";
            }
            if (result[i].equals("2")) {
                result[i] = "Silver Medal";
            }
            if (result[i].equals("3")) {
                result[i] = "Bronze Medal";
            }
        }
        return result;
    }
    

    }


  • 0
    9

    Seems like when you put to treemap, it takes O(nlogn)


  • 0
    S

    You don't have to do third loop.

        public String[] findRelativeRanks(int[] nums) {
            if (nums == null) {
                return null;
            }
            else if (nums.length == 0) {
                return new String[0];
            }
            int len = nums.length;
            TreeMap<Integer,Integer> map = new TreeMap<Integer,Integer>(Collections.reverseOrder());
            for(int i = 0; i < len; i ++) {
                map.put(nums[i], i);
            }
            String[] result = new String[len];
            int i = 1;
            for(Integer n : map.keySet()) {
                int v = map.get(n);
                result[v] = i == 1 ? "Gold Medal" : (i == 2 ? "Silver Medal" : (i == 3 ? "Bronze Medal" : String.valueOf(i)));
                i ++;
            }
            return result;
        }
    

Log in to reply
 

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