Li Kou daily question - day 26 -506 Relative rank

2022.6.24 Did you brush the questions today ？

---

subject ：

Give you a length of n Array of integers for score , among score[i] It's No i The score of an athlete in the game . All the scores are Different from each other .

The athlete will score according to Decide the ranking , Ranking No 1 Our athletes scored the highest , Ranking 2 Our athletes scored the third 2 high , And so on . The ranking of athletes determines their awards ：

Ranking 1 Our athletes won the gold medal "Gold Medal" .
Ranking 2 Our athletes won the silver medal "Silver Medal" .
Ranking 3 Our athletes won bronze "Bronze Medal" .
From the rank 4 To the first n Sportsmen , You can only get their ranking number （ namely , Ranking x Athletes get numbers "x"）.
The length used is n Array of answer Return to the winning , among answer[i] It's No i The awards of athletes .

analysis ：

Give you an array , The top three write “ gold medal ”,“ Silver medal ”,“ Bronze Medal ”, For others, just write the ranking , For example, if you are in the fourth place, write 4, Write when you are fifth 5. Note that this return must be based on the order of the given array .

Ideas ： Let's reverse the original array first , utilize sort and reverse. Then two for Loop through to see if the array elements are equal , Record its original subscript , Then record the return value for the corresponding subscript position of the returned string

analysis ：

1. Violent solution

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        vector<int>vec(score.size());
        int cnt = 0;
        vector<string>str(score.size());
        int idx = 0;
        for (int i = 0; i < score.size(); i++)
        {
            vec[i] = score[i];
        }
        sort(vec.begin(), vec.end());
        string s;
        reverse(vec.begin(), vec.end());
        for (auto i = 0; i < vec.size(); i++)
        {
            for (auto j = 0; j < score.size(); j++)
            {
                if (vec[i] == score[j])
                {
                    cnt++;
                    if (cnt == 1)
                    {
                        str[j]= "Gold Medal";
                    }
                    else if (cnt == 2)
                    {
                        str[j]  ="Silver Medal";
                    }
                    else if (cnt == 3)
                    {
                        str[j] = "Bronze Medal";
                    }
                    else 
                    {
                       
                        str[j] = to_string(cnt);
                    }
                }

            }
        }
        return str;
    }
};

2. Hashtable

The idea here is , Use a hash table to record the subscripts of the original data , The original data is also sorted during recording , Here the sorting takes advantage of , Reverse and store the original data , From big to small . According to the map To interpolate the subscript of the record

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& score) {
        vector<pair<int, int>>arr;
        int cnt = 0;
        vector<string>str(score.size());
        string desc[3] = { "Gold Medal", "Silver Medal", "Bronze Medal" };
        for (int i = 0; i < score.size(); i++)
        {
            arr.emplace_back(make_pair(-score[i], i));
        }
        sort(arr.begin(), arr.end());

        for (auto i = 0; i < score.size(); i++)
        {
            if (i >= 3) {
                str[arr[i].second] = to_string(i + 1);
            }
            else {
                str[arr[i].second] = desc[i];
            }

        }
        return str;
    }
};