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.
1#include <iostream>
2#include <vector>
3#include <algorithm>
4
5struct ScoreEntry {
6 int id;
7 double score;
8};
9
10bool compare(ScoreEntry a, ScoreEntry b) {
11 return a.score > b.score;
12}
13
14void assignRanks(std::vector<ScoreEntry>& entries) {
15 std::sort(entries.begin(), entries.end(), compare);
16 int rank = 1;
17 for (size_t i = 0; i < entries.size(); ++i) {
18 if (i == 0 || entries[i].score != entries[i - 1].score) {
19 rank = i + 1;
20 }
21 std::cout << "Score: " << entries[i].score << ", Rank: " << rank << std::endl;
22 }
23}
24
25int main() {
26 std::vector<ScoreEntry> scores = {
27 {1, 3.50}, {2, 3.65}, {3, 4.00}, {4, 3.85}, {5, 4.00}, {6, 3.65}
28 };
29 assignRanks(scores);
30 return 0;
31}The C++ solution utilizes a vector to hold score entries and the standard `sort` function with a lambda comparator for descending order. By iterating through the sorted scores, the rank is adjusted considering ties. This approach provides clear indexing with little overhead.
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
The C bucket sort implementation converts each score based on its proximity to MIN_SCORE using a defined bucket size. Each score increments its corresponding bucket to count occurrences. The ranks are assigned by iteratively checking non-empty buckets from highest to lowest.