给定一个整数数组，要求为每个元素计算其在升序排序后的数组中首次出现的索引位置（即按值排序后的“排名”，相同值按原顺序赋予连续但不重复的排名），时间复杂度最优可达 O(n log n)，空间复杂度 O(n)。
给定一个整数数组，要求为每个元素计算其在升序排序后的数组中**首次出现的索引位置**（即按值排序后的“排名”，相同值按原顺序赋予连续但不重复的排名），时间复杂度最优可达 o(n log n)，空间复杂度 o(n)。
要解决“将每个元素映射为其在排序后数组中的位置”这一问题，关键在于理解题意中的位置含义：它并非指该值在排序后所有出现位置的集合，而是指该元素在稳定排序（stable sort）后所占据的索引——更准确地说，是该元素对应值在排序后数组中首次出现的下标。观察示例：
- 输入：[33, 44, 33, 11, 22]
- 排序后（稳定）：[11, 22, 33, 33, 44]
- 对应位置（0-indexed）：
- 11 → 索引 0
- 22 → 索引 1
- 第一个 33 → 索引 2
- 第二个 33 → 索引 3（注意：不是 2，因为题目输出为 [2, 4, 3, 0, 1]，说明每个元素独立映射到其自身在排序后实际所在位置，而非“值的最小排名”）
⚠️ 重要澄清：输出 [2, 4, 3, 0, 1] 对应原数组各元素在排序后数组中的实际索引位置（即排序后该元素“落在哪里”），而非“该值的最小排名”。验证如下：
| 原数组索引 | 元素 | 在排序后数组 [11,22,33,33,44] 中的位置 |
|---|---|---|
| 0 | 33 | 第一个 33 出现在索引 2 → 2 |
| 1 | 44 | 出现在索引 4 → 4 |
| 2 | 33 | 第二个 33 出现在索引 3 → 3 |
| 3 | 11 | 出现在索引 0 → 0 |
| 4 | 22 | 出现在索引 1 → 1 |
✅ 因此，本质是：对原数组执行稳定排序，记录每个原始元素（含原始下标）在排序后序列中的新位置，再按原始顺序输出这些新位置。
✅ 推荐解法（Java，O(n log n) 时间 / O(n) 空间）
利用 IntStream 构建带索引的键值对，按值稳定排序，再构建位置映射：
import java.util.*;
import java.util.stream.Collectors;
import java.util.stream.IntStream;
public class RankMapper {
public static int[] mapToSortedPositions(int[] arr) {
if (arr == null || arr.length == 0) return new int[0];
// Step 1: 创建 (原始索引, 值) 对，并按值升序排序（天然稳定，因 IntStream.range 顺序不变）
List<Integer> indices = IntStream.range(0, arr.length)
.boxed()
.sorted(Comparator.comparingInt(i -> arr[i]))
.collect(Collectors.toList());
// Step 2: 构建结果数组 —— result[i] = 原索引 i 在排序后的新位置
int[] result = new int[arr.length];
for (int newPos = 0; newPos < indices.size(); newPos++) {
int originalIndex = indices.get(newPos);
result[originalIndex] = newPos;
}
return result;
}
// 测试
public static void main(String[] args) {
int[] input = {33, 44, 33, 11, 22};
int[] output = mapToSortedPositions(input);
System.out.println(Arrays.toString(output)); // [2, 4, 3, 0, 1]
}
}? 复杂度分析
- 时间复杂度：O(n log n) —— 主要开销在排序；其余遍历均为 O(n)。
- 空间复杂度：O(n) —— 存储索引列表和结果数组。
⚠️ 注意事项
- 稳定性至关重要：若使用不稳定的排序（如 Arrays.sort(primitive array)），相同值的相对顺序可能打乱，导致第二个 33 被错误排到第一个 33 前面，破坏映射一致性。上述解法通过 Comparator.comparingInt(i -> arr[i]) 对索引排序，天然保持原始顺序（因 i 递增），等价于稳定排序。
- 不推荐用 Map<Integer, List<Integer>> 记录所有位置再查表，不仅逻辑绕弯，且无法直接区分相同值的不同实例（需额外处理原始索引），易出错且空间冗余。
- 若需支持 null 或自定义对象，应改用 Integer 包装类型并确保 Comparator 安全处理。
✅ 总结
本题核心是建立“原始位置 ↔ 排序后位置”的双射关系。最优实践是：用索引作为代理进行稳定排序，再反向填充位置映射。该模式简洁、高效、可读性强，符合面试中对代码鲁棒性与时间复杂度意识的双重考察。
