---

1331. 数组序号转换

• 标签：数组、哈希表、排序
• 难度：简单

题目链接

• 1331. 数组序号转换 - 力扣

题目大意

描述：给定一个整数数组 $arr$，将数组中的每个元素替换为它在数组中的序号。序号从 $1$ 开始计数，相同数值的元素拥有相同的序号。

要求：返回替换后的数组。

说明：

• $0 \le arr.length \le 10^5$。
• $-10^9 \le arr[i] \le 10^9$。

示例：

• 示例 1：

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

• 示例 2：

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

解题思路

思路 1：排序 + 哈希映射

1. 核心思想

先对数组去重排序，将每个唯一值映射到它的序号（排名），然后遍历原数组替换为序号。

2. 具体步骤

第 1 步：对 $arr$ 去重得到唯一值集合。
第 2 步：将唯一值升序排序。
第 3 步：建立哈希映射，$sorted\_unique[i]$ 的序号为 $i + 1$。
第 4 步：遍历原数组，用映射替换每个元素。

3. 举例说明

以 $arr = [40, 10, 20, 30]$ 为例：

去重排序：$[10, 20, 30, 40]$

建立映射：

• $10 \to 1$
• $20 \to 2$
• $30 \to 3$
• $40 \to 4$

替换结果：$[4, 1, 2, 3]$。

思路 1：代码

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        # 去重排序
        sorted_unique = sorted(set(arr))
        # 建立值到序号的映射
        rank = {val: i + 1 for i, val in enumerate(sorted_unique)}
        # 替换原数组
        return [rank[x] for x in arr]

思路 1：复杂度分析

• 时间复杂度：$O(n \log n)$，排序耗时 $O(n \log n)$，遍历耗时 $O(n)$。
• 空间复杂度：$O(n)$，哈希表和去重后的排序数组占用 $O(n)$ 空间。

---

思路 2：原地修改（也可行）

如果希望节省空间，可以在排序后使用二分查找确定每个元素的排名，但思路 1 已经是最简洁高效的实现方式。