C# solution using SortedDictionary (with explanation)


  • 0
    R

    Explanation
    SortedDictionary keeps its entries ordered by key, so if the athlete's score is used as the key, and the index in the input array as the value, then indices can be iterated over according to the players rank. However, by default the keys are in ascending order, and here they need to be in descending order. For this purpose we can supply a custom comparer object; fortunately defining a new class isn't necessary, because there's a static method Comparer<T>.Create which accepts a comparison delegate and returns a comparer object using that delegate.
    After the dictionary is filled with nums[i] => i pairs the dictionary values (the indices in the nums array) are enumerated and athletes' ranks are put in the result array at those indices.

    public class Solution {
        public string[] FindRelativeRanks(int[] nums) {
            Comparer<int> reverseCmp = Comparer<int>.Create((x, y) => y - x);
            SortedDictionary<int, int> dict = new SortedDictionary<int, int>(reverseCmp);
            for (int i = 0; i < nums.Length; i++)
                dict.Add(nums[i], i);
            string[] result = new string[nums.Length];
            int place = 1;
            foreach (int index in dict.Values)
            {
                string rank;
                if (place == 1)
                    rank = "Gold Medal";
                else if (place == 2)
                    rank = "Silver Medal";
                else if (place == 3)
                    rank = "Bronze Medal";
                else
                    rank = place.ToString();
                result[index] = rank;
                place++;
            }
            return result;
        }
    }
    

    Performance
    SortedDictionary is implemented as a balanced tree and has logarithmic time of insert operations, so filling up the dictionary takes O(N*logN), and memory-wise it consumes O(n). Enumerating dictionary values is a linear time operation.
    Therefore, this implementation's complexity is O(N*logN) time and O(N) space.


Log in to reply
 

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