给定一个整数数组，要求为每个元素计算其在升序排序后的数组中首次出现的索引位置（即按值排序后的“排名”，相同值按原顺序赋予连续但不重复的排名），时间复杂度最优可达 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 <h3>? 复杂度分析</h3>
<ul>
<li>
<strong>时间复杂度</strong>：O(n log n) —— 主要开销在排序；其余遍历均为 O(n)。</li>
<li>
<strong>空间复杂度</strong>：O(n) —— 存储索引列表和结果数组。</li>
</ul>
<h3>⚠️ 注意事项</h3>
<ul>
<li>
<strong>稳定性至关重要</strong>：若使用不稳定的排序（如 Arrays.sort(primitive array)），相同值的相对顺序可能打乱，导致第二个 33 被错误排到第一个 33 前面，破坏映射一致性。上述解法通过 Comparator.comparingInt(i -> arr[i]) 对<strong>索引</strong>排序，天然保持原始顺序（因 i 递增），等价于稳定排序。</li>
<li>不推荐用 Map<integer list>> 记录所有位置再查表，不仅逻辑绕弯，且无法直接区分相同值的不同实例（需额外处理原始索引），易出错且空间冗余。</integer>
</li>
<li>若需支持 null 或自定义对象，应改用 Integer 包装类型并确保 Comparator 安全处理。</li>
</ul>
<h3>✅ 总结</h3>
<p>本题核心是建立“原始位置 ↔ 排序后位置”的双射关系。最优实践是：<strong>用索引作为代理进行稳定排序，再反向填充位置映射</strong>。该模式简洁、高效、可读性强，符合面试中对代码鲁棒性与时间复杂度意识的双重考察。</p></integer>
