1331. 数组序号转换

Posted on | In
Words count in article: 350 | Reading time ≈ 1

题目

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

  • 序号从 1 开始编号。

  • 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。

  • 每个数字的序号都应该尽可能地小。

示例 1:

1
2
3
输入：arr = [40,10,20,30]
输出：[4,1,2,3]
解释：40 是最大的元素。 10 是最小的元素。 20 是第二小的数字。 30 是第三小的数字。

示例2：

1
2
3
输入：arr = [100,100,100]
输出：[1,1,1]
解释：所有元素有相同的序号。

示例3：

1
2
输入：arr = [37,12,28,9,100,56,80,5,12]
输出：[5,3,4,2,8,6,7,1,3]

提示：

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

解法

解法一：

JAVA

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
public int[] arrayRankTransform(int[] arr) {
        if (null == arr || 0 == arr.length) {
            return new int[0];
        }

        int[] sorted = Arrays.copyOf(arr, arr.length);
        Arrays.sort(sorted);
        Map<Integer, Integer> map = new HashMap<>(sorted.length);
        int count = 1;
        int range = 1;
        int last = sorted[0];
        for (int i = 1;i < sorted.length;i++) {
            if (sorted[i] == last) {
                count++;
            } else {
                map.put(sorted[i - 1], range);
                range += 1;
                last = sorted[i];
                count = 1;
            }
        }
        if (0 != count) {
            map.put(sorted[sorted.length - 1], range);
        }

        int[] result = new int[arr.length];
        for (int i = 0;i < result.length;i++) {
            result[i] = map.get(arr[i]);
        }
        return result;
    }
0%