Easy Java Solution, Sorting.


  • 31

    Basically this question is to find out the score -> ranking mapping. The easiest way is to sort those scores in nums. But we will lose their original order. We can create (score , original index) pairs and sort them by score decreasingly. Then we will have score -> ranking (new index) mapping and we can use original index to create the result.

    Time complexity: O(NlgN). Space complexity: O(N). N is the number of scores.

    Example:
    
    nums[i]    : [10, 3, 8, 9, 4]
    pair[i][0] : [10, 3, 8, 9, 4]
    pair[i][1] : [ 0, 1, 2, 3, 4]
    
    After sort:
    pair[i][0] : [10, 9, 8, 4, 3]
    pair[i][1] : [ 0, 3, 2, 4, 1]
    
    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            int[][] pair = new int[nums.length][2];
            
            for (int i = 0; i < nums.length; i++) {
                pair[i][0] = nums[i];
                pair[i][1] = i;
            }
            
            Arrays.sort(pair, (a, b) -> (b[0] - a[0]));
            
            String[] result = new String[nums.length];
    
            for (int i = 0; i < nums.length; i++) {
                if (i == 0) {
                    result[pair[i][1]] = "Gold Medal";
                }
                else if (i == 1) {
                    result[pair[i][1]] = "Silver Medal";
                }
                else if (i == 2) {
                    result[pair[i][1]] = "Bronze Medal";
                }
                else {
                    result[pair[i][1]] = (i + 1) + "";
                }
            }
    
            return result;
        }
    }
    

    Also we can use an one dimension array. This will save a little bit space but space complexity is still O(n).

    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            Integer[] index = new Integer[nums.length];
            
            for (int i = 0; i < nums.length; i++) {
                index[i] = i;
            }
            
            Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));
            
            String[] result = new String[nums.length];
    
            for (int i = 0; i < nums.length; i++) {
                if (i == 0) {
                    result[index[i]] = "Gold Medal";
                }
                else if (i == 1) {
                    result[index[i]] = "Silver Medal";
                }
                else if (i == 2) {
                    result[index[i]] = "Bronze Medal";
                }
                else {
                    result[index[i]] = (i + 1) + "";
                }
            }
    
            return result;
        }
    }
    

  • 24

    Besides using a 2D array, you can also use another array to do sorting, with a map to map between the sorted array and the original array.

    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            int[] ranks = nums.clone(); 
            Arrays.sort(ranks);
            Map<Integer, Integer> map = new HashMap<>();
            for(int i = 0; i<ranks.length; i++){
                map.put(ranks[i], nums.length-i);
            }
            String[] res = new String[nums.length];
            for(int i = 0; i<nums.length; i++){
                int rank = map.get(nums[i]);
                String rankStr = rank+"";
                if(rank==1) rankStr = "Gold Medal";
                else if(rank==2) rankStr = "Silver Medal";
                else if(rank==3) rankStr = "Bronze Medal";
                res[i] = rankStr; 
            }
            return res; 
        }
    }
    

  • 0

    good solution, use nums.length - i in map. I reverse the sorted Array....


  • 0

    Arrays.sort(index, (a, b) -> (nums[b] - nums[a]));

    This part is genius


  • 0

    @Chidong yeah, it realize the Descending Sort. Soga.....


  • 0
    A

    Feels like the best solutions are either sort an array or use a priority queue.


  • 0
    R

    Python version:

    class Solution(object):
        def findRelativeRanks(self, nums):
            mp = {}
            as1 = list(nums)
            as1.sort(reverse=True)
            for k,v in enumerate(as1):
                if k == 0:
                    mp[v] = "Gold Medal"
                elif k == 1:
                    mp[v] = "Silver Medal"
                elif k == 2:
                    mp[v] = "Bronze Medal"
                else:
                    mp[v] = str(k + 1)
            arr = []
            for i in nums:
                arr.append(mp[i])
            return arr
    

    Javascript version:

    var findRelativeRanks = function(nums) {
            var ranks = nums.slice();
            ranks.sort(function(a, b) {return a-b});
            var mp = {}
            for(var i = 0; i < ranks.length; i++) {
                mp[ranks[i]] = nums.length-i;
            }
            var res = new Array(nums.length);
            for(var i =0; i < nums.length; i++) {
                var rank = mp[nums[i]]
                var rankStr = rank + "";
                if(rank==1) rankStr = "Gold Medal";
                else if(rank == 2) rankStr = "Silver Medal";
                else if (rank == 3) rankStr = "Bronze Medal";
                res[i] = rankStr;
            }
            return res;
    };
    

    Golang version:

    import ("sort"
            "strconv")
    
    func findRelativeRanks(nums []int) []string {
            ranks:=make([]int, len(nums))
            copy(ranks, nums)
            sort.Sort(ByInt(ranks));
            mp := make(map[int]int)
            for i := 0; i < len(ranks); i++ {
                mp[ranks[i]] = len(nums)-i
            }
            res := make([]string, len(nums))
            for i:=0; i < len(nums); i++ {
                rank := mp[nums[i]]
                rankStr := strconv.Itoa(rank)
                if rank==1 { rankStr = "Gold Medal" 
                    
                } else if rank == 2 {rankStr = "Silver Medal" 
                    
                } else if rank == 3 {rankStr = "Bronze Medal" }
                res[i] = rankStr
            }
            return res
    }
    
    type ByInt []int
    
    func (a ByInt) Len() int           { return len(a) }
    func (a ByInt) Swap(i, j int)      { a[i], a[j] = a[j], a[i] }
    func (a ByInt) Less(i, j int) bool { return a[i] < a[j] }
    
    
    

  • 3

    C++ version with a hash map: score -> index:

        vector<string> findRelativeRanks(vector<int>& nums) {
          unordered_map<int, int> num2Idx; int i = 0;
          for (int n : nums) num2Idx[n] = i++; // build map: num -> index
          sort(nums.begin(), nums.end());
          
          vector<string> rank(i), medals{"Gold Medal", "Silver Medal", "Bronze Medal"};
          for (int n : nums) rank[num2Idx[n]] = i>3? to_string(i--) : medals[--i];
          return rank;
        }
    

  • 1

    @Chidong said in Easy Java Solution, Sorting.:

    Besides using a 2D array, you can also use another array to do sort, with a map to map between the sorted array and the original array.

            int[] ranks = nums.clone(); 
            Arrays.sort(ranks);
    

    I think you could achieve the the same purpose without using an extra O(N) space to define array ranks[]. The hash map can be generated by nums and it doesn't matter in which order res[i] is assigned in terms of the index. Of course, your solution has the benefit not altering the original array nums[].


  • 0
    K

    @austurela take a look on my O(n) solution below


  • 1
    G

    In solution 2, why index has to be an Integer array instead of int array?


  • 0
    K

    @gogogoogle seems like we are talking about different solutions, here is the last one from me on this problem https://discuss.leetcode.com/topic/78588/java-6ms-solution-o-n-without-sorting


  • 1

    @gogogoogle This is one of the shortcoming of Java Arrays class. It only support public static <T> void sort(T[] a, Comparator<? super T> c) The T here has to be an Object, can't be a primitive type.

    https://docs.oracle.com/javase/8/docs/api/java/util/Arrays.html#sort-T:A-java.util.Comparator-


  • 0
    M

    @Chidong This is a best solution and easy to understand. map.get(i) returns the value of that key, which is nums[i]. clever trick to link rank[] and nums[]!

    20ms for 17 test cases


  • 1
    N

    said in Easy Java Solution, Sorting.:

    (a, b) -> (nums[b] - nums[a])

    Can you clarify this detail? Are there any documentations for this "->" operator?


  • 1

    @noboundaries It is called Lambda Expressions, introduced in Java 8. You can refer to http://docs.oracle.com/javase/tutorial/java/javaOO/lambdaexpressions.html
    Basically it same as

    Arrays.sort(index, new Comparator<Integer>{
       @Override 
       public int compare(Integer a, Integer b){
           return nums[b] - nums[a];
       }
    });
    
    

  • 0
    N

    @Chidong Now it makes a lot more sense. Thank you so much for the prompt reply!


  • 4
    A

    @zzg_zzm
    Using no extra space to clone the array.
    Time: O(nlogn) -> Sorting
    Space: O(n) -> HashMap

    public class Solution {
        public String[] findRelativeRanks(int[] nums) {
            String[] result = new String[nums.length];
            HashMap<Integer, Integer> map = new HashMap<>();
            for (int i=0; i<nums.length; i++) {
                map.put(nums[i], i);
            }
            Arrays.sort(nums);
            for (int i=0; i<nums.length; i++) {
                if (i == nums.length-1)
                    result[map.get(nums[i])] = "Gold Medal";
                else if (i == nums.length-2)
                    result[map.get(nums[i])] = "Silver Medal";
                else if (i == nums.length-3)
                    result[map.get(nums[i])] = "Bronze Medal";
                else
                    result[map.get(nums[i])] = (nums.length - i)+"";
            }
            return result;
        }
    }

  • 0
    F

    Good solution!
    In fact,i think we could use just one simple array to solve the question.For there will be no more than 10000 elements in the array, and that's my code

           public String[] findRelativeRanks(int[] nums) {
            long[] sort = new long[nums.length];
            for(int i=0;i<nums.length;i++){
                sort[i]=nums[i]*10000+i;
            }
            Arrays.sort(sort);
            String[] result = new String[nums.length];
            for(int i=nums.length-1;i>=0;i--){
                if(i==(nums.length-1)){
                    result[(int)(sort[i]%10000)]="Gold Medal";
                }else if(i==(nums.length-2)){
                    result[(int)(sort[i]%10000)]="Silver Medal";
                }else if(i==(nums.length-3)){
                    result[(int)(sort[i]%10000)]="Bronze Medal";
                }else{
                    result[(int)(sort[i]%10000)]=(nums.length-i)+"";
                }
            }
            return result;
        }
    

    sort[i]=nums[i]*10000+i;
    the order of sort is the same with thr origin arrays.Besides,we could sort[i]%10000 to get the index in the origin array,


  • 0
    G

    Same strategy slightly concise

    public class Solution {
        private String[] medals = {"Gold Medal", "Silver Medal", "Bronze Medal"};
        
        public String[] findRelativeRanks(int[] nums) {
            int len = nums.length;
            String[] output = new String[len];
            
            Map<Integer, Integer> reverseMap = new HashMap<>(len);
            
            for(int i=0; i<len; i++) reverseMap.put(nums[i], i);
            
            Arrays.sort(nums);
            
            for(int i=len-1; i>-1; i--) output[reverseMap.get(nums[i])] = getText(len-i-1);
            
            return output;
            
        }
        
        private String getText(int rank) {
            return (rank < medals.length) ? medals[rank] : String.valueOf(rank+1);
        }
    }
    

Log in to reply
 

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