Sponsored
This approach involves sorting the scores in descending order, then iteratively assigning ranks to each score while handling ties appropriately. This can be efficiently achieved using a sorting algorithm followed by a traversal to assign ranks. By maintaining an index while sorting, we can assign ranks directly to the original scores.
Time Complexity: O(n log n) due to the sorting operation.
Space Complexity: O(1), only a fixed amount of additional memory is used for sorting.
1using System;
2using System.Collections.Generic;
3
4class ScoreEntry {
5 public int Id { get; set; }
6 public double Score { get; set; }
7}
8
9class Program {
10 static void AssignRanks(List<ScoreEntry> scores) {
11 scores.Sort((a, b) => b.Score.CompareTo(a.Score));
12 int rank = 1;
13 for (int i = 0; i < scores.Count; i++) {
14 if (i == 0 || scores[i].Score != scores[i - 1].Score) {
15 rank = i + 1;
16 }
17 Console.WriteLine($"Score: {scores[i].Score:F2}, Rank: {rank}");
18 }
19 }
20
21 static void Main() {
22 List<ScoreEntry> scores = new List<ScoreEntry> {
23 new ScoreEntry { Id = 1, Score = 3.50 },
24 new ScoreEntry { Id = 2, Score = 3.65 },
25 new ScoreEntry { Id = 3, Score = 4.00 },
26 new ScoreEntry { Id = 4, Score = 3.85 },
27 new ScoreEntry { Id = 5, Score = 4.00 },
28 new ScoreEntry { Id = 6, Score = 3.65 }
29 };
30
31 AssignRanks(scores);
32 }
33}C# uses a List to hold score entries and sorts it using a lambda function for comparison in descending order. It then processes the sorted scores to assign ranks, appropriately handling ties with the same methodology as the other implementations.
This approach uses a bucket sort strategy, particularly efficient when scores have a limited range of decimal places. This reduces the complexity substantially in scenarios where HTTP (High Throughput Processing) is required. Counting occurrences of each score allows direct assignment of ranks in descending order of scores efficiently.
Time Complexity: O(n + k), where n is the number of scores, and k is the number of buckets (constant in this case).
Space Complexity: O(k), which is fixed and depends on BUCKET_COUNT.
1
Python uses a Counter from the collections module to tally the scores into bucketed indices. It then processes these counts in descending order of buckets to output ranks efficiently. This bucket implementation relies on Python's ability to handle large integers and dynamic indexing smartly.