JavaScript非负整数数组非递减排序后输出原索引求解

问题说明 #

给定长度为m的非负整数数组A，需要先将数组按非递减规则完成排序，最终输出排序后新数组中每个元素对应的原始数组索引（索引从0开始计数）。

示例参考
原数组：A = [4,5,3,7,1]
非递减排序后数组：[1,3,4,5,7]
对应要求输出结果：4 2 0 1 3

实现逻辑 #

• 不直接对原始元素值做排序，先把每个元素和它的原始索引绑定为一组数据，避免排序后丢失原始位置信息
• 排序时仅以每组中的元素值作为排序依据，按非递减规则排列
• 排序完成后，按顺序提取每组里存的原始索引，拼接成要求的输出格式即可
• 若存在值相等的元素，保持其原有相对顺序即可，不会违反非递减的排序要求

代码示例（Python） #

def sorted_original_index(arr):
    # 生成(元素值, 原始索引)的配对列表
    val_index_pairs = [(val, idx) for idx, val in enumerate(arr)]
    # 按元素值升序排列配对列表
    val_index_pairs.sort(key=lambda item: item[0])
    # 提取索引并拼接为空格分隔的结果字符串
    return " ".join(str(pair[1]) for pair in val_index_pairs)

# 验证示例
if __name__ == "__main__":
    test_arr = [4,5,3,7,1]
    print(sorted_original_index(test_arr))  # 运行输出：4 2 0 1 3

内容的提问来源于stack exchange，提问作者Ashiq Khan