E1331.数组序号转换

implementation, https://leetcode.cn/problems/rank-transform-of-an-array/

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

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

序号从 1 开始编号。
一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
每个数字的序号都应该尽可能地小。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

0 <= arr.length <= 10^5
-10^9 <= arr[i] <= 10^9

这个问题可以通过排序和哈希表来解决。具体步骤如下：

解题思路

去重并排序：通过 set(arr) 去除数组中的重复元素，然后使用 sorted() 进行升序排序。排序后的数组中，每个元素的索引（加 1）即为其对应的序号。
建立映射关系：遍历排序后的唯一元素列表，使用哈希表（Python 中的字典）存储每个元素与其序号的映射关系。
生成结果数组：遍历原数组 arr，利用哈希表将每个元素替换为其对应的序号。

Python 3 实现

python

from typing import List

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        # 1. 去重并排序
        sorted_unique = sorted(set(arr))
        
        # 2. 建立元素到序号的映射关系
        rank_map = {num: i + 1 for i, num in enumerate(sorted_unique)}
        
        # 3. 根据映射关系转换原数组
        return [rank_map[num] for num in arr]

复杂度分析

时间复杂度： $O (N \log N)$ ，其中 $N$ 是数组 arr 的长度。去重操作需要 $O (N)$ 时间，排序长度最多为 $N$ 的数组需要 $O (N \log N)$ 时间，建立哈希表和重构数组分别需要 $O (N)$ 时间。
空间复杂度： $O (N)$ ，用于存储去重后的数组以及哈希表映射关系。

E1331.数组序号转换 ​

E1331.数组序号转换