如何高效计算数组中不相等的两数配对数量（Python）-图灵python

给定一个长度 n 整数组需要快速统计所有下标不同但元素值不同的二元组 (i, j)（i
给定一个长度 n 整数组需要快速统计所有下标不同但元素值不同的二元组 (i, j)（i

处理大规模数组(例如 n = 10⁵）当暴力枚举所有组合(共约)时 5×10⁹ 是的)会严重超时。使用原始方案 itertools.combinations(arr, 2) 比较值是否相等，时间复杂度为 O(n²)，无法通过 500ms 时限。

基于补充思想的更好解决方案：先计算所有可能的无序标记总数，然后减去「值相等」配对数，即：
配对数不相等 = 总配对数 − 相等配对数
总配对数：从 n 在中间选择个元素 2 个，即组合数 C(n, 2) = n * (n - 1) // 2；

相等配对数：对每个重复出现的值 x(频率为 v），它的内部可以构成 C(v, 2) = v * (v - 1) // 2 相等配对；和谐所有值的值。

该算法只需要一次统计频率（O(n)），再次历频字典(最多) O(n) 整个时间的复杂度是不同的值)， O(n)，空间复杂度为 O(u)（u 对于不同元素的数量)，完全满足大数据量的要求。

以下是完全实现：

Python数据分析助手
为业务和科研数据的快速处理提供Python数据清理、统计分析和可视化建议。

下载
from collections import Counter

def count_different_pairs(n, arr):
    # 统计每个数字的频率
    freq = Counter(arr)

    # 总无序对数：C(n, 2)
    total_pairs = n * (n - 1) // 2

    # 所有值相等的配对数之和
    same_pairs = sum(v * (v - 1) // 2 for v in freq.values())

    return total_pairs - same_pairs

# 示例验证
n = 3
arr = [1, 7, 1]
print(count_different_pairs(n, arr))  # 输出：2

# 测试用例较多
print(count_different_pairs(4, [2, 2, 2, 2]))  # 0（全相同）
print(count_different_pairs(4, [1, 2, 3, 4]))  # 6（全不同 → C(4,2)=6）
✅ 注意事项：

立即学习“Python免费学习笔记(深入)；

任意整数(包括负数、零)都可以输入数组元素，Counter 完全支持；

使用整数除法 // 避免浮点误差；

不依赖下标顺序，只关注值的分布，因此不需要排序或额外索引结构；

如果需要返回具体配对(而不仅仅是数量)，则必须返回到 O(n²) 方法-本题目只计数，因此优化成立。

该方法是典型的“计数优化”范式：避免显式结构，转而利用数学归纳和频率聚合实现线性突破。