Sponsored
Sponsored
This approach involves sorting the array to determine the rank of each element. After sorting, unique elements are mapped to their ranks.
Time Complexity: O(N log N) due to sorting.
Space Complexity: O(N) for storing the sorted array and rank map.
1#include <vector>
2#include <map>
3#include <algorithm>
4using namespace std;
5
6vector<int> arrayRankTransform(vector<int>& arr) {
7 vector<int> sorted = arr;
8 sort(sorted.begin(), sorted.end());
9
10 map<int, int> rankMap;
11 int rank = 1;
12 for (int num : sorted) {
13 if (rankMap.find(num) == rankMap.end()) {
14 rankMap[num] = rank++;
15 }
16 }
17
18 vector<int> result;
19 for (int num : arr) {
20 result.push_back(rankMap[num]);
21 }
22 return result;
23}This C++ solution employs sorting and a map to keep track of ranks. The sorted unique elements are mapped to incremental ranks, and these ranks are then assigned to the original array elements.
Coordinate compression is a method to map large ranges of numbers to smaller ranges, maintaining their relative order. This approach uses this idea to assign ranks.
Time Complexity: O(N log N) due to sorting and binary search operations.
Space Complexity: O(N) for rank maps.
1#include <stdio.h>
2#include
The C coordinate compression solution involves sorting the array and creating a rank map by compressing coordinates. This map is used for rank assignment efficiently.