如何按元素大小为列表生成索引值？要求单循环实现高性能

核心思路 #

要兼顾单循环要求和极高性能，优先利用语言内置的高效排序（底层为C实现，远快于手动循环逻辑），再通过一次循环完成结果映射。核心逻辑：

• 先对原列表元素排序，生成元素与对应位次的映射（位次从1开始，按元素从小到大顺序分配）
• 用单循环遍历原列表，通过映射表直接替换每个元素为对应位次

代码实现（Python） #

def rank_elements(arr):
    # 内置排序生成有序列表，创建元素到位次的映射（O(n log n)，性能远超手动实现）
    sorted_arr = sorted(arr)
    rank_map = {val: idx + 1 for idx, val in enumerate(sorted_arr)}
    # 单循环生成最终结果
    return [rank_map[val] for val in arr]

# 测试示例
original = [5,7,83,1]
result = rank_elements(original)
print(result)  # 输出: [2,3,4,1]

性能说明 #

• 时间复杂度：O(n log n)，主要来自排序操作，这是此类问题的最优时间复杂度（排序无法低于O(n log n)）
• 空间复杂度：O(n)，用于存储有序列表和映射表
• 结果生成阶段为单循环，且映射表查找是O(1)哈希操作，性能拉满

重复元素场景扩展（可选） #

如果列表存在重复元素，需相同元素对应相同位次，可调整映射表生成逻辑：

def rank_elements_with_duplicates(arr):
    sorted_arr = sorted(arr)
    rank_map = {}
    current_rank = 1
    for val in sorted_arr:
        if val not in rank_map:
            rank_map[val] = current_rank
            current_rank += 1
    return [rank_map[val] for val in arr]

# 测试重复元素
original = [5,7,5,1]
result = rank_elements_with_duplicates(original)
print(result)  # 输出: [2,3,2,1]

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