[1331. Array serial number conversion]

source ： Power button （LeetCode）

describe ：

Give you an array of integers arr , Please replace each element in the array with their ordinal number after sorting .

The serial number represents how big an element is . The rules for serial numbers are as follows ：

• The serial number from 1 Numbered starting .
• The bigger an element is , So the bigger the serial number . If two elements are equal , So they have the same serial number .
• The serial number of each number should be as small as possible .

Example 1：

 Input ：arr = [40,10,20,30]
 Output ：[4,1,2,3]
 explain ：40  It's the biggest element . 10  It's the smallest element . 20  It's the second smallest number . 30  It's the third smallest number .

Example 2：

 Input ：arr = [100,100,100]
 Output ：[1,1,1]
 explain ： All elements have the same sequence number .

Example 3：

 Input ：arr = [37,12,28,9,100,56,80,5,12]
 Output ：[5,3,4,2,8,6,7,1,3]

Tips ：

• 0 <= arr.length <= 10⁵
• -10⁹ <= arr[i] <= 10⁹

Method ： Sort + Hashtable

Ideas

First, save the sorted original array with an array , Then use a hash table to save the sequence number of each element , Finally, replace the elements of the original group with sequence numbers and return .

Code :

class Solution {
    
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
    
        vector<int> sortedArr = arr;
        sort(sortedArr.begin(), sortedArr.end());
        unordered_map<int, int> ranks;
        vector<int> ans(arr.size());
        for (auto &a : sortedArr) {
    
            if (!ranks.count(a)) {
    
                ranks[a] = ranks.size() + 1;
            }
        }
        for (int i = 0; i < arr.size(); i++) {
    
            ans[i] = ranks[arr[i]];
        }
        return ans;
    }
};

Execution time ：100 ms, In all C++ Defeated in submission 39.83% Users of
Memory consumption ：38.3 MB, In all C++ Defeated in submission 46.48% Users of
Complexity analysis
Time complexity ：O(n × logn), among n Is the input array arr The length of , Sorting costs O(n × logn) Time .
Spatial complexity ：O(n). Consumption of ordered array and hash table O(n) Space .
arthor：LeetCode-Solution