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-解题思路分析/
此条目发表在leetcode分类目录,贴了, , , 标签。将固定链接加入收藏夹。

发表评论

您的电子邮箱地址不会被公开。