Python中如何构建整数为键、列表为值的Map？含时间复杂度分析

输入数组 #

arr = [1,2,1,3,4,2,4,2]

需求目标 #

将数组元素作为映射（Map）的键，对应元素的所有索引组成的列表作为映射的值，最终得到结果：

mp = {1:[0,2],2:[1,5,7],3:[3],4:[4,6]}

实现代码（Python） #

arr = [1,2,1,3,4,2,4,2]
mp = {}
for idx, num in enumerate(arr):
    # 若元素未在映射中，初始化空列表
    if num not in mp:
        mp[num] = []
    # 将当前索引添加到对应元素的列表中
    mp[num].append(idx)

时间复杂度分析 #

该方案只需遍历数组一次，遍历过程中对哈希表的操作（键存在性判断、列表追加元素）均为O(1)的常数时间操作，因此整体时间复杂度为O(n)，其中n是输入数组的长度。

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