Python实现按列表元素首次出现顺序为重复项分配对应编号

核心需求 #

• 遍历输入的嵌套列表，每遇到首次出现的新子元素，为其分配从0开始逐次递增的编号
• 后续遇到重复出现的元素，直接复用该元素首次出现时分配的编号

测试用例说明 #

基础测试场景 #

输入：

[[1, 1], [1, 1], [2, 2], [1, 1], [1, 1], [2, 2], [3, 3], [4, 4]]

期望输出：

[0, 0, 1, 0, 0, 1, 2, 3]

扩展测试场景 #

子列表允许包含两个不等值的元素，比如输入加入[2,1]后：

[[1, 1], [1, 1], [2, 2], [1, 1], [2, 1], [2, 2], [3, 3], [4, 4]]

对应正确输出应为：

[0, 0, 1, 0, 2, 1, 3, 4]

现有实现的不足 #

你之前写的实现虽然逻辑正确，但每次判断重复都要对原列表做切片遍历，还需要调用index顺序查找元素位置，整体时间复杂度为O(n²)，列表长度较大时运行效率很低，代码也偏冗余：

line = [[1, 1], [1, 1], [2, 2], [1, 1], [2, 1], [2, 2], [3, 3], [4, 4]]
p = []
line_not = []
k = 0
for i in range (len(line)):
    if line[i] in line[:i]:
        p.append(line_not[:k].index(line[i]))
    else:
        p.append(k)
        line_not.append(line[i])
        k+=1

优化方案 #

用字典做哈希映射存储「元素值 -> 分配编号」的对应关系，字典查找的时间复杂度为O(1)，整体逻辑时间复杂度可以降到O(n)，代码也更简洁：

line = [[1, 1], [1, 1], [2, 2], [1, 1], [2, 1], [2, 2], [3, 3], [4, 4]]
id_map = {}
res = []
for sub_list in line:
    # 列表是可变类型不可哈希，转成元组作为字典键
    key = tuple(sub_list)
    if key not in id_map:
        id_map[key] = len(id_map)
    res.append(id_map[key])

方案说明 #

• 字典的长度正好就是下一个要分配的递增编号，不需要额外维护计数变量
• 不需要每次切片遍历原列表判断元素是否出现过，也不需要顺序查找已存元素的索引，长列表下性能提升明显
• 两个测试场景跑出来的结果完全符合预期

小提示：如果后续子列表的嵌套层级更深，可以把转元组的逻辑换成递归转不可变类型，只要保证作为键的对象可哈希就能正常运行。

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