1331. 数组序号转换

🟢   🔖  数组 哈希表 排序  🔗 力扣 LeetCode

题目

Given an array of integers arr, replace each element with its rank.

The rank represents how large the element is. The rank has the following rules:

• Rank is an integer starting from 1.
• The larger the element, the larger the rank. If two elements are equal, their rank must be the same.
• Rank should be as small as possible.

Example 1:

Input: arr = [40,10,20,30]

Output: [4,1,2,3]

Explanation : 40 is the largest element. 10 is the smallest. 20 is the second smallest. 30 is the third smallest.

Example 2:

Input: arr = [100,100,100]

Output: [1,1,1]

Explanation : Same elements share the same rank.

Example 3:

Input: arr = [37,12,28,9,100,56,80,5,12]

Output: [5,3,4,2,8,6,7,1,3]

Constraints:

• 0 <= arr.length <= 10^5
• -10^9 <= arr[i] <= 10^9

题目大意

给你一个整数数组 arr ，请你将数组中的每个元素替换为它们排序后的序号。

序号代表了一个元素有多大。序号编号的规则如下：

• 序号从 1 开始编号。
• 一个元素越大，那么序号越大。如果两个元素相等，那么它们的序号相同。
• 每个数字的序号都应该尽可能地小。

解题思路

1. 对数组的副本进行去重，并从小到大排序
2. 使用一个哈希表存储排序后数组中每个数字的排序
3. 再次遍历原数组，在哈希表中查找出排序后返回

复杂度分析

• 时间复杂度：O(n log n)，排序的时间复杂度是 O(n log n)。
• 空间复杂度：O(n)，用于存储哈希表和排序后的数组副本。

代码

/**
 * @param {number[]} arr
 * @return {number[]}
 */
var arrayRankTransform = function (arr) {
	const sorted = [...new Set(arr)].sort((a, b) => a - b);

	let map = new Map();
	for (let i = 0; i < sorted.length; i++) {
		map.set(sorted[i], i + 1);
	}

	return arr.map((i) => map.get(i));
};

相关题目

题号	标题	题解	标签	难度
1632	矩阵转换后的秩		并查集 图 拓扑排序 3+
2089	找出数组排序后的目标下标		数组 二分查找 排序