# LeetCode 1331. Rank Transform of an Array

https://leetcode.com/problems/rank-transform-of-an-array/description/

## 題目大意

把整數陣列 `arr` 的元素替換成其大小順序的排名 (排名從 `1` 開始)

## 思考

類似的概念好像也不是第一次出現了

我們就在排序 `arr` 的內容時多塞原始 index 以便之後寫回正確位置

class Solution
{
public:
    vector<int> arrayRankTransform(vector<int> &arr)
    {
        if (arr.empty())
            return {};

        const int n = arr.size();
        vector<pair<int, int>> sortedArr(n);
        for (int i = 0; i < n; ++i)
        {
            sortedArr[i] = {arr[i], i};
        }

        sort(sortedArr.begin(), sortedArr.end());

        auto begin = sortedArr.begin(), end = sortedArr.end();
        int rank = 1;
        arr[begin->second] = 1;

        for (auto it = next(begin); it != end; ++it)
        {
            if (it->first != prev(it)->first)
                ++rank;
            arr[it->second] = rank;
        }

        return arr;
    }
};

`sortedArr.begin()->first` 就會是最小的元素， `rank` 依題意為 `1`
其在 `arr` 的位置即 `arr[sortedArr.begin()->second]`

之後的元素如果跟前一個不一樣表示 `rank` 該變大了
然後同理找到對應位置 `arr[it->second]` 把它替換成當下的 `rank`