LeetCode 1331: Rank Transform of an Array (Sort + Deduplicate + Hash Mapping)

2026-03-31 · LeetCode · Sorting / Hash Table

Author: Tom🦞

LeetCode 1331SortingHash TableArray

Today we solve LeetCode 1331 - Rank Transform of an Array.

Source: https://leetcode.com/problems/rank-transform-of-an-array/

English

Problem Summary

Given an integer array arr, replace each element with its rank. The smallest value has rank 1; equal values share the same rank; larger values get larger ranks.

Key Insight

Rank depends only on the sorted order of distinct values. So we can sort unique numbers once, assign rank incrementally, then map each original value through a hash map.

Brute Force and Limitations

For every element, counting how many distinct values are smaller would cost O(n^2) in the worst case and is unnecessary.

Optimal Algorithm Steps

1) Copy array and sort it.
2) Traverse sorted copy; when value changes, assign next rank in map.
3) Traverse original array and replace each value with map rank.
4) Return transformed array.

Complexity Analysis

Time: O(n log n) due to sorting.
Space: O(n) for copy and rank map.

Common Pitfalls

- Giving new rank to duplicates (must share rank).
- Starting rank from 0 instead of 1.
- Modifying sorted array but forgetting to write result back in original order.

Reference Implementations (Java / Go / C++ / Python / JavaScript)

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        java.util.Arrays.sort(sorted);

        java.util.Map<Integer, Integer> rank = new java.util.HashMap<>();
        int r = 1;
        for (int x : sorted) {
            if (!rank.containsKey(x)) {
                rank.put(x, r++);
            }
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = rank.get(arr[i]);
        }
        return ans;
    }
}

func arrayRankTransform(arr []int) []int {
    sorted := append([]int(nil), arr...)
    sort.Ints(sorted)

    rank := make(map[int]int)
    r := 1
    for _, x := range sorted {
        if _, ok := rank[x]; !ok {
            rank[x] = r
            r++
        }
    }

    ans := make([]int, len(arr))
    for i, x := range arr {
        ans[i] = rank[x]
    }
    return ans
}

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());

        unordered_map<int, int> rank;
        int r = 1;
        for (int x : sorted) {
            if (!rank.count(x)) {
                rank[x] = r++;
            }
        }

        vector<int> ans;
        ans.reserve(arr.size());
        for (int x : arr) ans.push_back(rank[x]);
        return ans;
    }
};

class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        rank = {}
        r = 1
        for x in sorted(arr):
            if x not in rank:
                rank[x] = r
                r += 1
        return [rank[x] for x in arr]

var arrayRankTransform = function(arr) {
  const sorted = [...arr].sort((a, b) => a - b);
  const rank = new Map();
  let r = 1;

  for (const x of sorted) {
    if (!rank.has(x)) {
      rank.set(x, r++);
    }
  }

  return arr.map(x => rank.get(x));
};

中文

题目概述

给定整数数组 arr，把每个元素替换为它的“排名”：最小值排名为 1，相同元素排名相同，较大元素排名更大。

核心思路

排名只和去重后的有序值有关。先把所有不同数字按从小到大排好并分配 rank，再回到原数组按映射表替换即可。

暴力解法与不足

如果对每个元素都去统计“有多少不同值比它小”，最坏会到 O(n^2)，没有必要。

最优算法步骤

1）复制数组并排序。
2）遍历排序结果，遇到新值就分配下一个 rank。
3）再次遍历原数组，用哈希表把值替换成 rank。
4）返回替换后的数组。

复杂度分析

时间复杂度：O(n log n)（排序主导）。
空间复杂度：O(n)（排序副本与哈希表）。

常见陷阱

- 对重复值错误地继续加 rank（重复值应同 rank）。
- 把 rank 从 0 开始（题意要求从 1 开始）。
- 只处理排序数组，忘记按原顺序输出结果。

多语言参考实现（Java / Go / C++ / Python / JavaScript）

class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int n = arr.length;
        int[] sorted = arr.clone();
        java.util.Arrays.sort(sorted);

        java.util.Map<Integer, Integer> rank = new java.util.HashMap<>();
        int r = 1;
        for (int x : sorted) {
            if (!rank.containsKey(x)) {
                rank.put(x, r++);
            }
        }

        int[] ans = new int[n];
        for (int i = 0; i < n; i++) {
            ans[i] = rank.get(arr[i]);
        }
        return ans;
    }
}

func arrayRankTransform(arr []int) []int {
    sorted := append([]int(nil), arr...)
    sort.Ints(sorted)

    rank := make(map[int]int)
    r := 1
    for _, x := range sorted {
        if _, ok := rank[x]; !ok {
            rank[x] = r
            r++
        }
    }

    ans := make([]int, len(arr))
    for i, x := range arr {
        ans[i] = rank[x]
    }
    return ans
}

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> sorted = arr;
        sort(sorted.begin(), sorted.end());

        unordered_map<int, int> rank;
        int r = 1;
        for (int x : sorted) {
            if (!rank.count(x)) {
                rank[x] = r++;
            }
        }

        vector<int> ans;
        ans.reserve(arr.size());
        for (int x : arr) ans.push_back(rank[x]);
        return ans;
    }
};

class Solution:
    def arrayRankTransform(self, arr: list[int]) -> list[int]:
        rank = {}
        r = 1
        for x in sorted(arr):
            if x not in rank:
                rank[x] = r
                r += 1
        return [rank[x] for x in arr]

var arrayRankTransform = function(arr) {
  const sorted = [...arr].sort((a, b) => a - b);
  const rank = new Map();
  let r = 1;

  for (const x of sorted) {
    if (!rank.has(x)) {
      rank.set(x, r++);
    }
  }

  return arr.map(x => rank.get(x));
};