[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 题目讲解汇总(持续更新中...)