C++ using map and unordered_map


  • 0
    B

    we need to sort the index of number by the value of number

    the lazy way is to use STL map, the value of number is key, and the index of number is value

    then in-order traverse the map, and assign the order to index with a hashMap

    then traverse the index to find the rank of each element

    The overall time complexity is O(n log n), dominant by the insertion to map
    The space complexity is O(n), we store n elements in each map

    class Solution {
    public:
        vector<string> findRelativeRanks(vector<int>& nums) {
            map<int,int>order;
            unordered_map<int,int>result;
            vector<string>ans;
            for(int i = 0; i < nums.size(); i++) order[nums[i]] = i;
            int rank = nums.size();
            for(auto e : order) result[e.second] = rank--;
                
            for(int i = 0; i < nums.size(); i++)
            {
                int val = result[i];
                if(val == 1)
                {
                    ans.push_back("Gold Medal");
                }
                else if(val == 2)
                {
                    ans.push_back("Silver Medal");
                }
                else if(val == 3)
                {
                    ans.push_back("Bronze Medal");
                }
                else
                {
                    ans.push_back(to_string(val));
                }
            }
            return ans;
        }
    };

Log in to reply
 

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