题目形容

这是 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多平台公布