Sponsored
Sponsored
The idea is to sort the scores but preserve their original indices by pairing each score with its index. Once sorted, we can easily determine their ranks by iterating over the sorted list. We then assign the corresponding rank values based on their positions (i.e., 'Gold Medal' for the first position, etc.). This approach utilizes additional space to maintain the original indices while sorting the scores.
Time Complexity: O(n log n), where n is the number of scores, for the sorting operation.
Space Complexity: O(n) for storing the pair struct array and the result array.
1using System;
2using System.Collections.Generic;
3
4public class Solution {
5 public string[] FindRelativeRanks(int[] score) {
6 int n = score.Length;
7 List<Tuple<int, int>> scoreIndex = new List<Tuple<int, int>>();
8
9 for (int i = 0; i < n; i++) {
10 scoreIndex.Add(new Tuple<int, int>(score[i], i));
11 }
12
13 scoreIndex.Sort((a, b) => b.Item1.CompareTo(a.Item1));
14
15 string[] result = new string[n];
16 string[] medals = { "Gold Medal", "Silver Medal", "Bronze Medal" };
17
18 for (int i = 0; i < n; i++) {
19 if (i < 3) {
20 result[scoreIndex[i].Item2] = medals[i];
21 } else {
22 result[scoreIndex[i].Item2] = (i + 1).ToString();
23 }
24 }
25 return result;
26 }
27}
28In this C# solution, use of Tuple enables pairing the scores with indices. We leverage the Sort method coupled with a lambda expression to order the scores in descending order. Based on the sorted order, ranks are assigned back to the result array using original indices.
In this approach, we employ a hash map (or dictionary) to map each score to its ranking position in a sorted list. The scores are first sorted to determine order-based ranks. We then iterate through original scores, using the map to quickly assign the appropriate ranking (medal or numeric) to each score.
Time Complexity: O(n log n) from sorting.
Space Complexity: O(n) due to storage of the sorted copy.
1#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;
vector<string> findRelativeRanks(vector<int>& score) {
vector<int> sortedScores = score;
unordered_map<int, int> rankMap;
sort(sortedScores.rbegin(), sortedScores.rend());
for (int i = 0; i < sortedScores.size(); ++i) {
rankMap[sortedScores[i]] = i;
}
vector<string> result(score.size());
string medals[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
for (int i = 0; i < score.size(); ++i) {
int rank = rankMap[score[i]];
if (rank < 3) {
result[i] = medals[rank];
} else {
result[i] = to_string(rank + 1);
}
}
return result;
}
This C++ solution uses a map to store the rank for each score based on a sorted version of the scores. After sorting the scores in descending order, it builds a map of each score to its rank; this allows for quick rank determination directly from the score array by looking up each score in the map.