1331. 數組序号轉換 : 簡單模拟題

題目描述

這是 LeetCode 上的 ​​1331. 數組序号轉換​​ ，難度為 簡單。

Tag : 「模拟」、「哈希表」、「排序」

給你一個整數數組 ​

​arr​

​，請你将數組中的每個元素替換為它們排序後的序号。

序号代表了一個元素有多大。序号編号的規則如下：

• 序号從
• 一個元素越大，那麼序号越大。如果兩個元素相等，那麼它們的序号相同。
• 每個數字的序号都應該盡可能地小。

示例 1：

輸入：arr = [40,10,20,30]

輸出：[4,1,2,3]      

示例 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]      

提示：

模拟

根據題意進行模拟即可。

對 ​

​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      

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      

• 時間複雜度：
• 空間複雜度：

最後

這是我們「刷穿 LeetCode」系列文章的第 ​

​No.1331​

​ 篇，系列開始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道題目，部分是有鎖題，我們将先把所有不帶鎖的題目刷完。

在這個系列文章裡面，除了講解解題思路以外，還會盡可能給出最為簡潔的代碼。如果涉及通解還會相應的代碼模闆。