共计 1445 个字符，预计需要花费 4 分钟才能阅读完成。
题目形容
这是 LeetCode 上的 1331. 数组序号转换 ，难度为 简略。
Tag :「模仿」、「哈希表」、「排序」
给你一个整数数组 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$
模仿
依据题意进行模仿即可。
对 arr 进行拷贝操作失去新数组 clone，对 clone 数组进行排序，再应用哈希表记录元素与序号的映射关系，最初依据映射关系结构答案。
Java 代码：
class Solution {public int[] arrayRankTransform(int[] arr) {int[] clone = arr.clone();
Arrays.sort(clone);
Map<Integer, Integer> map = new HashMap<>();
int n = arr.length, idx = 0;
for (int i : clone) {if (!map.containsKey(i)) map.put(i, ++idx);
}
int[] ans = new int[n];
for (int i = 0; i < n; i++) ans[i] = map.get(arr[i]);
return ans;
}
}TypeScript 代码：
function arrayRankTransform(arr: number[]): number[] {let clone = new Array<number>()
for (const i of arr) clone.push(i)
clone.sort((a,b)=>a-b)
let n = arr.length, idx = 0
let map = new Map<number, number>()
for (const i of clone) {if (!map.has(i)) map.set(i, ++idx)
}
let ans = new Array<number>()
for (let i = 0; i < n; i++) ans.push(map.get(arr[i]))
return ans
};- 工夫复杂度：$O(n\log{n})$
- 空间复杂度：$O(n)$
最初
这是咱们「刷穿 LeetCode」系列文章的第 No.1331 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，局部是有锁题，咱们将先把所有不带锁的题目刷完。
在这个系列文章外面，除了解说解题思路以外，还会尽可能给出最为简洁的代码。如果波及通解还会相应的代码模板。
为了不便各位同学可能电脑上进行调试和提交代码，我建设了相干的仓库：https://github.com/SharingSou…。
在仓库地址里，你能够看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其余优选题解。
更多更全更热门的「口试 / 面试」相干材料可拜访排版精美的 合集新基地 🎉🎉
本文由 mdnice 多平台公布
正文完
