1331. Rank Transform of an Array

O(nlogn) time O(n) space

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        auto A = arr;
        sort(begin(A), end(A));
        unordered_map<int, int> m;
        for (int x : A) {
            m.emplace(x, size(m) + 1); // insert重复key会失败，只有第一个会keep
        }
        for (int i = 0; i < size(arr); ++i) {
            A[i] = m[arr[i]];
        }
        return A;
    }
};

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> A = arr;
        sort(begin(A), end(A));
        unordered_map<int, int> m;
        int i = 0;
        for (int x : A) {
            m[x] = m.count(x) ? m[x] : ++i;
        }
        vector<int> res;
        for (int x : arr) {
            res.push_back(m[x]);
        }
        return res;
    }
};