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 题目讲解汇总(持续更新中…)
（欢迎加入博主的知识星球，博主将及时答疑解惑，并分享刷题经验与总结，快快加入吧～）
喜欢请点赞，疼爱请打赏❤️.
微信打赏
|
Venmo 打赏
—|—
转载请注明来源于 Grandyang 的博客 (grandyang.com)，欢迎对文章中的引用来源进行考证，欢迎指出任何有错误或不够清晰的表达。可以在下面评论区评论，也可以邮件至 grandyang@qq.com
