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.
1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
4
5struct ScoreIndex {
6 int score;
7 int index;
8};
9
10int compare(const void *a, const void *b) {
11 return ((struct ScoreIndex*)b)->score - ((struct ScoreIndex*)a)->score;
12}
13
14char **findRelativeRanks(int* score, int scoreSize, int* returnSize) {
15 struct ScoreIndex scoreIndex[scoreSize];
16 char **result = (char **)malloc(scoreSize * sizeof(char *));
17 const char *medals[] = {"Gold Medal", "Silver Medal", "Bronze Medal"};
18
19 for (int i = 0; i < scoreSize; i++) {
20 scoreIndex[i].score = score[i];
21 scoreIndex[i].index = i;
22 }
23
24 qsort(scoreIndex, scoreSize, sizeof(struct ScoreIndex), compare);
25
26 for (int i = 0; i < scoreSize; i++) {
27 if (i < 3) {
28 result[scoreIndex[i].index] = strdup(medals[i]);
29 } else {
30 result[scoreIndex[i].index] = (char *)malloc(10 * sizeof(char));
31 sprintf(result[scoreIndex[i].index], "%d", i + 1);
32 }
33 }
34
35 *returnSize = scoreSize;
36 return result;
37}
38The solution involves creating a pair structure (ScoreIndex) to hold both the score and its original index. We make use of qsort to sort the array in descending order based on scores. After sorting, the rank is assigned according to the sorted position, converting the top three into medal strings and others into strings of their positions. Finally, the ranks are filled into the result array based on 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.
1using System;
using System.Collections.Generic;
public class Solution {
public string[] FindRelativeRanks(int[] score) {
int[] sortedScores = new int[score.Length];
Array.Copy(score, sortedScores, score.Length);
Array.Sort(sortedScores, (a, b) => b.CompareTo(a));
Dictionary<int, int> rankMap = new Dictionary<int, int>();
for (int i = 0; i < sortedScores.Length; i++) {
rankMap[sortedScores[i]] = i;
}
string[] result = new string[score.Length];
string[] medals = { "Gold Medal", "Silver Medal", "Bronze Medal" };
for (int i = 0; i < score.Length; i++) {
int rank = rankMap[score[i]];
result[i] = rank < 3 ? medals[rank] : (rank + 1).ToString();
}
return result;
}
}
In C#, the solution leverages a Dictionary to hold mappings of each score to its corresponding rank, which is derived from a sorted list of scores. This precise mapping facilitates rank retrieval when iterating over the original scores array, adapting medals where necessary.