如何高效查找二维数组中含唯一门店ID的州ID

我有一个二维数组，外层数组的索引代表StateID（州ID），内层数组的整数代表StoreIDs（门店ID）：

StoreStateList = [[1,2],[1,2,3],[1,3,7,9],[1,8,12],[7,9,12]]

需求是找到包含至少一个「其他州都没有的门店」的州，比如示例中的州3（索引为3），它的门店8在其他州都不存在。

当前我用4层嵌套循环实现，但效率极低，代码如下（注：原代码存在变量名不一致、语法错误及逻辑问题）：

def findUniqueStore(StoreRegionList):
    for state in range(len(StoreRegionList)):
        state_count = 0
        for store in StoreStateList[state]:
            # 检查该门店是否出现在其他州
            for state_inner in range(len(StoreRegionList)):
                for store_inner in StoreStateList[state_inner]:
                    if store == store_inner:
                        state_count += 1
        if state_count == 1:
            return state

高效解法思路 #

核心是先统计所有门店的出现频率，再快速判断每个州是否存在唯一门店，步骤如下：

1. 统计门店出现次数：用字典（哈希表）遍历所有门店，记录每个门店在全局的出现次数（假设每个州内门店ID不重复，次数为1即代表该门店仅属于一个州）。
2. 遍历每个州检查：对每个州，遍历其门店，只要存在任意一个门店的出现次数为1，就返回该州ID。

实现代码 #

def find_unique_store(StoreStateList):
    # 第一步：统计所有门店的出现次数
    store_counts = {}
    for state_stores in StoreStateList:
        for store in state_stores:
            store_counts[store] = store_counts.get(store, 0) + 1
    
    # 第二步：遍历每个州，检查是否有唯一门店
    for state_id, state_stores in enumerate(StoreStateList):
        for store in state_stores:
            if store_counts[store] == 1:
                return state_id
    # 无符合条件的州时返回None
    return None

# 测试示例
StoreStateList = [[1,2],[1,2,3],[1,3,7,9],[1,8,12],[7,9,12]]
print(find_unique_store(StoreStateList))  # 输出3

效率对比 #

• 原代码时间复杂度：O(K²)，K为总门店数，每个门店都要和所有门店逐一比对。
• 优化后时间复杂度：O(K)，仅需两次遍历所有门店，哈希表操作平均时间复杂度为O(1)。

原代码的问题说明 #

1. 变量名不一致：函数参数为StoreRegionList，但内部引用StoreStateList，会导致运行报错。
2. 逻辑错误：state_count统计的是该州所有门店的全局总出现次数，即使存在唯一门店，其他门店的次数累加后也会远大于1，无法正确触发返回。
3. 嵌套层级过多：4层循环导致数据量大时效率极低，卡顿明显。

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