已排序数组中统计重复元素配对数的单循环实现方法咨询

完全可以通过单次循环实现统计，时间复杂度为O(n)，相比双层循环的O(n²)方案性能提升极大，尤其适合处理长数组场景。

实现思路 #

• 利用已排序数组相同元素连续排列的特性，遍历过程中记录当前连续重复元素的个数
• 对于连续出现k次的相同元素，可形成的配对数为组合数C(k,2) = k*(k-1)/2，累加所有连续重复段的配对数即可得到最终结果

示例代码（Java实现） #

public int countDuplicatePairs(int[] sortedArr) {
    // 边界情况处理：数组长度不足2时不存在配对
    if (sortedArr == null || sortedArr.length < 2) {
        return 0;
    }
    int totalPairs = 0;
    int currentRepeatCount = 1;
    for (int i = 1; i < sortedArr.length; i++) {
        if (sortedArr[i] == sortedArr[i - 1]) {
            currentRepeatCount++;
        } else {
            // 累加当前重复段的配对数
            totalPairs += currentRepeatCount * (currentRepeatCount - 1) / 2;
            currentRepeatCount = 1;
        }
    }
    // 补充累加最后一段重复元素的配对数
    totalPairs += currentRepeatCount * (currentRepeatCount - 1) / 2;
    return totalPairs;
}

验证示例 #

以你给出的数组{1, 1, 1, 2, 3, 3}为例：

• 元素1连续出现3次，贡献配对数：3*2/2=3
• 元素2仅出现1次，贡献配对数：0
• 元素3连续出现2次，贡献配对数：2*1/2=1
• 总配对数3+0+1=4，和示例结果完全匹配。

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