如何在O(1)时间复杂度下查询列表元素位置（避免转元组）

首先是你已经实现的列表分组代码：

L = [[1], [2], [3], [1,2], [2,3], [1,2,3]]
L1, L2, L3 = [], [], []
for x in L:
    if len(x) == 1:
        L1.append(x)
    elif len(x) == 2:
        L2.append(x)
    elif len(x) == 3:
        L3.append(x)

你的核心需求是：遍历L3中的元素，对每个元素生成去掉第i个元素后的子列表（长度为2，属于L2的元素类型），以O(1)时间找到该子列表在L2中的位置，但由于数据规模极大，希望避免将列表转换为元组作为字典键。

以下是几个可行的替代方案：

方案1：针对固定长度子列表，用多层字典映射元素值 #

由于你的L2中都是长度为2的列表，L3生成的子列表也都是长度为2，可以直接用列表的元素值构建多层字典，完全不需要转换元组：

L = [[1], [2], [3], [1,2], [2,3], [1,2,3]]
L1, L2, L3 = [], [], []
# 构建各列表的位置映射：L2用双层字典，键为元素值
pos_l1 = {}
pos_l2 = {}  # 结构：{第一个元素: {第二个元素: 位置索引}}
pos_l3 = {}

for x in L:
    if len(x) == 1:
        val = x[0]
        pos_l1[val] = len(L1)
        L1.append(x)
    elif len(x) == 2:
        a, b = x
        if a not in pos_l2:
            pos_l2[a] = {}
        pos_l2[a][b] = len(L2)
        L2.append(x)
    elif len(x) == 3:
        a, b, c = x
        if a not in pos_l3:
            pos_l3[a] = {}
        if b not in pos_l3[a]:
            pos_l3[a][b] = {}
        pos_l3[a][b][c] = len(L3)
        L3.append(x)

# 执行查找逻辑
for x in L3:
    for i in range(len(x)):
        sub = x[:i] + x[i+1:]
        a, b = sub
        # O(1)时间获取位置
        print(pos_l2[a][b])

这个方案的优势：

• 完全避免元组转换，内存开销更小
• 查找是严格O(1)，无哈希冲突风险
• 逻辑直观，适合固定长度的列表场景

方案2：自定义列表哈希函数（适用于可变长度场景） #

如果你的列表长度不固定，可以自定义一个哈希函数，直接基于列表元素计算哈希值，替代元组的哈希：

def hash_list(lst):
    """自定义列表哈希函数，降低冲突概率"""
    hash_val = 0
    base = 911382629  # 大质数，减少冲突
    for elem in lst:
        hash_val = hash_val * base + hash(elem)
    return hash_val

L = [[1], [2], [3], [1,2], [2,3], [1,2,3]]
L1, L2, L3 = [], [], []
pos = {}

for x in L:
    key = hash_list(x)
    if len(x) == 1:
        pos[key] = len(L1)
        L1.append(x)
    elif len(x) == 2:
        pos[key] = len(L2)
        L2.append(x)
    elif len(x) == 3:
        pos[key] = len(L3)
        L3.append(x)

# 查找逻辑
for x in L3:
    for i in range(len(x)):
        sub = x[:i] + x[i+1:]
        sub_hash = hash_list(sub)
        # 若担心哈希冲突，可额外加一层列表内容校验
        # if pos[sub_hash]对应的L2元素和sub内容一致再返回
        print(pos[sub_hash])

注意事项：

• 自定义哈希函数仍存在极小的冲突概率，若数据规模极大且要求绝对准确，需要在查找时额外比较列表内容
• 哈希函数的效率取决于元素类型和列表长度，对于整数元素来说，这个方法的性能接近元组哈希

方案3：利用列表的内存地址（仅适用于子列表为原对象引用的场景） #

如果生成的子列表x[:i]+x[i+1:]和L2中的列表是同一个内存对象（即不是新创建的列表），可以直接用列表的id()作为键：

L = [[1], [2], [3], [1,2], [2,3], [1,2,3]]
L1, L2, L3 = [], [], []
pos = {}

for x in L:
    key = id(x)
    if len(x) == 1:
        pos[key] = len(L1)
        L1.append(x)
    elif len(x) == 2:
        pos[key] = len(L2)
        L2.append(x)
    elif len(x) == 3:
        pos[key] = len(L3)
        L3.append(x)

# 注意：此方法仅当sub是L2中原有列表的引用时有效
# 比如如果L3中的元素是直接引用L中的[1,2,3]，x[:i]+x[i+1:]是新列表，id不同，此方法失效

这个方法局限性很大，仅适用于子列表未被重新创建的场景，一般不推荐。

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