如何在C++中对数组排序并获取排序后元素的原始索引位置？

需求概述 #

给定原始数值数组，要求在不改变原数组元素顺序的前提下，生成一个新数组，其中每个元素是原数组对应元素在升序排序后数组中的1-based索引。

举个例子：

• 原始数组：[66,43,642]
• 升序排序后的数组：[43,66,642]
• 目标结果数组：[2,1,3]

实现方案（以Python为例） #

核心步骤 #

1. 对原始数组进行复制后升序排序，避免修改原数组的内容和顺序
2. 遍历原始数组的每个元素，找到其在排序后数组中的索引，再加1转换为1-indexed格式

代码示例 #

original = [66, 43, 642]
# 复制并排序，不改动原数组
sorted_arr = sorted(original)
# 生成结果
result = [sorted_arr.index(num) + 1 for num in original]
print(result)  # 输出: [2, 1, 3]

特殊情况处理 #

如果原始数组包含重复元素，上述方法会返回重复元素第一次出现的索引。如果需要为重复元素区分不同位置，可以通过记录元素的原始索引来处理，示例如下：

original = [66, 43, 66, 642]
# 生成带原始索引的元组列表，排序后保留位置信息
sorted_with_indices = sorted((val, idx) for idx, val in enumerate(original))
# 构建值到1-based位置的映射，处理重复值
pos_map = {}
for pos, (val, idx) in enumerate(sorted_with_indices, 1):
    if val not in pos_map:
        pos_map[val] = []
    pos_map[val].append(pos)
# 生成结果，按原始顺序分配位置
result = []
for val in original:
    result.append(pos_map[val].pop(0))
print(result)  # 输出: [2, 1, 3, 4]

内容的提问来源于stack exchange，提问作者Jane Doe