[LeetCode] 1331. Rank Transform of an Array 數組序號轉換

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

Rank is an integer starting from 1.
The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]
Output: [4,1,2,3]
Explanation: 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]
Output: [1,1,1]
Explanation: Same elements share the same rank.

Example 3:

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

Constraints:

0 <= arr.length <= 105
-109 <= arr[i] <= 109

這道題給了一個數組 arr，說是讓把每個數字替換為其在該數組中大小的 rank 值，數字越大其 rank 值越大，最小的數字的 rank 值為1，逐漸增大。對于相同的數字其 rank 值相同，而下一個數字的 rank 值不能因之前有相同的 rank 值而跳過空位。雖說是道簡單的題目，但還是有一定的技巧的。此題的核心就是需要知道每個數字的 rank 值，但是給定的數組是亂序的，所以可以直接排個序，這樣數字就是有序的了。

我們可以建立每個數字和其 rank 值之間的映射，這樣之后就能快速的知道每個數字的 rank 值，從而返回正確的 rank 值數組。博主剛開始的想法是每個數字的映射值就是其下標加1，但是這種更新方法在存在相同數字時就不正確了。正確方法是維護一個 rank 變量，初始化為1，然后遍歷排序后的數字，對于遍歷到的數字，若其不在 HashMap 中，則賦予其當前 rank 值，然后 rank 值自增1。這樣可以保證跳過所有相同的數字，使得后面不同的數字都賦上正確的 rank 值，參見代碼如下：

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        int rank = 1;
        unordered_map<int, int> rankMap;
        vector<int> nums = arr;
        sort(nums.begin(), nums.end());
        for (int num : nums) {
            if (rankMap.count(num)) continue;
            rankMap[num] = rank++;
        }
        for (int &num : arr) {
            num = rankMap[num];
        }
        return arr;
    }
};

Github 同步地址:

https://github.com/grandyang/leetcode/issues/1331

類似題目：

Rank Transform of a Matrix

Find Target Indices After Sorting Array

參考資料：

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

https://leetcode.com/problems/rank-transform-of-an-array/solutions/489753/java-c-python-hashmap/

LeetCode All in One 題目講解匯總(持續更新中...)