Python高效统计数组中(x,y)与(y,x)唯一配对数的方法

直接删除元素的方法时间复杂度为O(n²)（每次查找配对都要遍历数组），数组规模较大时效率极低。改用哈希表统计频率的方法可将时间复杂度降至O(n)，具体步骤如下：

1. 转换元素类型：将数组中的每个子列表转为元组（列表无法作为字典键），方便后续统计。
2. 统计频率：用collections.Counter统计每个元组的出现次数，此步骤为线性时间复杂度。
3. 计算有效配对数：遍历每个唯一元组，计算它与逆序元组的可配对数量，同时标记已处理元组避免重复计算。

代码实现 #

from collections import Counter

def count_pairs(arr):
    # 转换为元组并统计各元组出现次数
    tuple_counts = Counter(tuple(item) for item in arr)
    count = 0
    processed = set()
    
    for t in tuple_counts:
        if t in processed:
            continue
        rev_t = (t[1], t[0])
        # 处理(x,x)这类自身逆序的情况
        if t == rev_t:
            count += tuple_counts[t] // 2
            processed.add(t)
        else:
            # 取两个元组出现次数的较小值作为可配对数量
            if rev_t in tuple_counts:
                count += min(tuple_counts[t], tuple_counts[rev_t])
                # 标记两个元组均已处理，避免重复统计
                processed.add(t)
                processed.add(rev_t)
    return count

# 测试示例1
arr1 = [[1,2], [2,1], [3,1]]
print(count_pairs(arr1))  # 输出1

# 测试示例2
arr2 = [[1,2], [2,1], [2,1]]
print(count_pairs(arr2))  # 输出1

效率说明 #

• 统计频率阶段为线性遍历，时间复杂度O(n)。
• 遍历唯一元组阶段的时间复杂度为O(k)（k为数组中不同元组的数量，k≤n），整体仍为O(n)。
• 避免了删除元素带来的数组移位开销，大幅提升大数组场景下的运行效率。

额外说明 #

• 对于(x,x)形式的元素（如[[2,2], [2,2]]），代码会将其计为1对，符合“每个配对仅计数一次”的逻辑。
• processed集合确保每个无序对仅被计算一次，不会重复统计(1,2)和(2,1)。

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