题目
给你一个整数数组 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 开始,相同元素跳过)。最后遍历原数组取哈希表中序号放回去返回。
代码
class Solution {
public int[] arrayRankTransform(int[] arr) {
int n = arr.length;
if (n == 0) return arr;
if (n == 1) {
arr[0] = 1;
return arr;
}
int[] sorted = new int[n];
System.arraycopy(arr, 0, sorted, 0, n);
Arrays.sort(sorted);
Map<Integer, Integer> map = new HashMap<>();
int curr, prev = sorted[0], count = 0;
map.put(prev, ++count);
for (int i = 1; i < n; i++) {
curr = sorted[i];
if (curr != prev) {
map.put(curr, ++count);
prev = curr;
}
}
for (int i = 0; i < n; i++) arr[i] = map.get(arr[i]);
return arr;
}
}
class Solution {
public:
vector<int> arrayRankTransform(vector<int>& arr) {
vector<int> sorted(arr);
sort(sorted.begin(), sorted.end());
unordered_map<int, int> mp;
int count = 0;
for (const int& num : sorted) {
if (!mp.count(num)) mp[num] = ++count;
}
for (auto it = arr.begin(); it != arr.end(); it++) *it = mp[*it];
return arr;
}
};
评论区