LEETCODE 1331. Rank Transform of an Array 解题思路分析

题目大意：

数组序号转换

给你一个整数数组 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 <= 105
• -109 <= arr[i] <= 109

---

如果想查看本题目是哪家公司的面试题，请参考以下免费链接： https://leetcode.jp/problemdetail.php?id=1331

解题思路分析：

本题难度不大，实现步骤大致如下：

1. 先copy一份数组
2. 将原数组排序
3. 给排序后数组中的每个数字按照大小进行排名编号，并存入HashMap中，其中key为该数字，value为排名编号
4. 遍历copy数组，查看当前数字在map中的编号，并将编号赋值给当前位。

实现代码：

public int[] arrayRankTransform(int[] arr) {
    // 先copy一份数组，作为返回结果
    int[] res=Arrays.copyOf(arr,arr.length);
    // 将原数组排序
    Arrays.sort(arr);
    // 记录每个数字的排名
    Map<Integer, Integer> map=new HashMap<>();
    // 初始排名为1
    int rank=1;
    // 循环排序好之后的每个数字
    for(int i=0;i<arr.length;i++){
        // 如果当前数字大于前数字，排名加一
        if(i>0&&arr[i]>arr[i-1]) rank++;
        // 将当前数字和排名存入map
        map.put(arr[i], rank);
    }
    // 循环copy数组
    for(int i=0;i<res.length;i++){
        // 取得当前数字的排名，并赋值给当前位
        res[i]=map.get(res[i]);
    }
    return res;
}

本题解法执行时间为24ms。

Runtime: 24 ms, faster than 94.58% of Java online submissions for Rank Transform of an Array.

Memory Usage: 55.6 MB, less than 100.00% of Java online submissions for Rank Transform of an Array.

本网站文章均为原创内容，并可随意转载，但请标明本文链接
如有任何疑问可在文章底部留言。为了防止恶意评论，本博客现已开启留言审核功能。但是博主会在后台第一时间看到您的留言，并会在第一时间对您的留言进行回复！欢迎交流！
本文链接: http://leetcode.jp/leetcode-1331-rank-transform-of-an-array-解题思路分析/