Easy

题目描述

给定一个整数数组 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

解题思路

这道题的核心思路是为数组中的每个元素分配一个基于大小关系的秩值。

基本思路：

  1. 首先需要确定数组中所有不同元素的相对大小关系
  2. 为每个不同的元素分配一个从1开始的连续秩值
  3. 将原数组中的每个元素替换为对应的秩值

具体实现步骤：

  1. 创建原数组的副本并排序，这样可以确定元素的大小顺序
  2. 使用哈希表建立元素值到秩的映射关系。遍历排序后的数组，为每个不同的元素分配递增的秩值
  3. 遍历原数组，使用哈希表将每个元素替换为对应的秩值

时间优化： 也可以先对数组去重再排序，这样在某些情况下可以减少排序的元素个数，但整体时间复杂度不变。

这种方法简单直观，利用排序确定大小关系，用哈希表实现O(1)的查找，是解决此类排名问题的经典方法。

代码实现

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> sorted_arr = arr;
        sort(sorted_arr.begin(), sorted_arr.end());
        
        unordered_map<int, int> rank_map;
        int rank = 1;
        
        for (int num : sorted_arr) {
            if (rank_map.find(num) == rank_map.end()) {
                rank_map[num] = rank++;
            }
        }
        
        vector<int> result;
        for (int num : arr) {
            result.push_back(rank_map[num]);
        }
        
        return result;
    }
};

class Solution:
    def arrayRankTransform(self, arr: List[int]) -> List[int]:
        sorted_arr = sorted(arr)
        rank_map = {}
        rank = 1
        
        for num in sorted_arr:
            if num not in rank_map:
                rank_map[num] = rank
                rank += 1
        
        return [rank_map[num] for num in arr]

public class Solution {
    public int[] ArrayRankTransform(int[] arr) {
        int[] sortedArr = new int[arr.Length];
        Array.Copy(arr, sortedArr, arr.Length);
        Array.Sort(sortedArr);
        
        Dictionary<int, int> rankMap = new Dictionary<int, int>();
        int rank = 1;
        
        foreach (int num in sortedArr) {
            if (!rankMap.ContainsKey(num)) {
                rankMap[num] = rank++;
            }
        }
        
        int[] result = new int[arr.Length];
        for (int i = 0; i < arr.Length; i++) {
            result[i] = rankMap[arr[i]];
        }
        
        return result;
    }
}

var arrayRankTransform = function(arr) {
    const sortedArr = [...arr].sort((a, b) => a - b);
    const rankMap = new Map();
    let rank = 1;
    
    for (const num of sortedArr) {
        if (!rankMap.has(num)) {
            rankMap.set(num, rank++);
        }
    }
    
    return arr.map(num => rankMap.get(num));
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型复杂度说明
时间复杂度O(n log n)主要由排序操作决定，其中 n 是数组长度
空间复杂度O(n)需要额外的排序数组和哈希表存储映射关系

相关题目