LeetCode 每日一题笔记

0. 前言

• 日期：2026.07.12
• 题目：1331. 数组序号转换
• 难度：简单
• 标签：数组、排序、哈希表

1. 题目理解

问题描述： 给定整数数组 arr，将数组内每个元素替换为排序后的序号；序号从1开始，元素越大序号越大，相等元素共用同一个序号，且每个数字的序号取最小可能值。

示例：

输入：arr = [40,10,20,30] 输出：[4,1,2,3] 解释：排序后数组 [10,20,30,40]，10序号1、20序号2、30序号3、40序号4，按原数组映射得到结果。

输入：arr = [100,100,100] 输出：[1,1,1] 解释：全部元素相等，共用序号1。

2. 解题思路

核心观察

1. 元素的序号由数组升序排序后的去重顺序决定，相同元素只分配一次序号；
2. 不能直接对原数组排序，需要拷贝副本排序，保留原数组顺序用于映射；
3. 使用哈希表存储「数值-对应序号」映射，最后遍历原数组完成替换。

算法步骤

1. 完整拷贝原数组得到副本 copy；
2. 对副本数组进行升序排序；
3. 遍历排序后的副本，去重并给每个唯一数字分配自增序号存入哈希map；
4. 再次遍历原数组，通过map查询每个数字对应的序号覆盖原数组元素；
5. 返回转换完成的原数组。

3. 代码实现

package lc1300_lc1399.lc1331;

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] copy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(copy);
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 1;
        for (int i : copy) {
            if (map.containsKey(i)) {
                continue;
            } else {
                map.put(i, count++);
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = map.get(arr[i]);
        }
        return arr;
    }
}

4. 代码优化说明

{减少if分支判断} 优化思路：利用 map.putIfAbsent 内置方法替代if-else分支，一行完成判断与存入，精简代码分支。

package lc1300_lc1399.lc1331;

import java.util.Arrays;
import java.util.HashMap;

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int[] copy = Arrays.copyOf(arr, arr.length);
        Arrays.sort(copy);
        HashMap<Integer, Integer> map = new HashMap<>();
        int count = 1;
        for (int num : copy) {
            // putIfAbsent：key不存在才存入，存在直接跳过，省去if判断分支
            if(map.putIfAbsent(num, count) == null){
                count++;
            }
        }
        for (int i = 0; i < arr.length; i++) {
            arr[i] = map.get(arr[i]);
        }
        return arr;
    }
}

5. 复杂度分析

• 时间复杂度：O(n log n) n为数组长度，主要耗时为数组排序；两次线性遍历、哈希存取均为O(n)，不影响量级。
• 空间复杂度：O(n) 需要开辟同等长度拷贝数组，哈希表最多存储n个唯一元素，最坏全不重复时占用O(n)空间。

6. 总结

1. 排序映射类题型通用套路：拷贝数组排序+哈希建立数值映射；
2. putIfAbsent 可简化去重赋值的分支判断，代码更简洁；
3. 原地修改原数组返回可节约额外数组空间，适合刷题场景；
4. 边界注意：全重复数字、单元素空数组，哈希自动去重逻辑可兼容全部边界。