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 ，请你将数组中的每个元素替换为它们排序后的序号。
序号代表了一个元素有多大。序号编号的规则如下：
序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/rank-transform-of-an-array
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题意不难理解，我们需要对 input 数组中的所有数字做一个 rank，rank 从 1 开始，最小的数字的 rank 就是 1。注意 input 数组中有重复数字。
这道题我提供一个 hashmap 的思路。首先我们克隆一份 input 数组，并对这个克隆排序，记为 sorted 数组。然后我们遍历这个 sorted 数组，对于每一个 unique 的元素，我们把他存入 hashmap，key 是这个元素，value 是当前 map.size() + 1。value的含义正好对应了题意要求的 rank。再次扫描原来的 input 数组，得到每个元素在 hashmap 里对应的 rank。
时间O(n)
空间O(n)
Java实现
1 class Solution {
2 public int[] arrayRankTransform(int[] arr) {
3 int[] sorted = arr.clone();
4 Arrays.sort(sorted);
5 HashMap<Integer, Integer> map = new HashMap<>();
6 for (int num : sorted) {
7 map.putIfAbsent(num, map.size() + 1);
8 }
9 for (int i = 0; i < arr.length; i++) {
10 arr[i] = map.get(arr[i]);
11 }
12 return arr;
13 }
14 }