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 同步地址:

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

（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）

喜欢请点赞，疼爱请打赏❤️~.~

微信打赏

|

Venmo 打赏

---|---