本文介绍一种时间复杂度为 o(n) 的数学优化方法，避免暴力枚举所有数对，适用于 n ≤ 10⁵ 的大规模输入场景。
本文介绍一种时间复杂度为 o(n) 的数学优化方法，避免暴力枚举所有数对，适用于 n ≤ 10⁵ 的大规模输入场景。
在解决“统计数组中值不相等的两元素组合数量”问题时，直观思路是使用 itertools.combinations(arr, 2) 遍历所有 C(n,2) 个数对并逐一比较——但该方法时间复杂度为 O(n²)，当 n = 10⁵ 时，需处理近 50 亿次比较，远超 500ms 时限。
更优解法基于补集思想：
不相等数对数量 = 总数对数量 − 值相等的数对数量
总数对数量为组合数：
[ \binom{n}{2} = \frac{n \times (n - 1)}{2} ]值相等的数对，仅可能出现在相同数字的重复出现中。若某数值
x在数组中出现v次，则它自身可构成C(v,2) = v × (v−1) // 2个相等数对。
因此，只需一次遍历统计频次（如用 collections.Counter），再分别计算总对数与同值对数即可。
以下是完整、高效、可直接提交的实现：
from collections import Counter
def count_different_pairs(n, arr):
total_pairs = n * (n - 1) // 2
freq = Counter(arr)
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
✅ 时间复杂度：O(n)，仅需两次线性扫描（Counter 构建 + 频次求和）；
✅ 空间复杂度：O(u)，u 为数组中不同元素个数，最坏为 O(n)；
⚠️ 注意事项：
- 输入
n可能为 1，此时n*(n−1)//2 = 0，无需额外判断； - 使用整数除法
//确保结果为整型，避免浮点误差； - 不建议在循环内重复调用
len()或count()，本解法完全规避此类开销。
该方法不仅满足 500ms 时限要求，且代码简洁、逻辑清晰，是处理大规模组合计数类问题的典型数学优化范式。
Python免费学习笔记（深入）：立即使用
在学习笔记中，你将探索 Python 的核心概念和高级技巧！
