1.4.8

1.4.8 #

解答 #

平方级别：直接二层循环遍历一遍。

线性对数：

先对数组排序，然后遍历一遍数组，在遍历过程中计算重复元素的数量，

然后用公式 $1+2+\cdots+n-1=n(n-1)/2$ 计算重复整数对的数量。

代码 #

/// <summary>
/// 暴力查找数组中相等的整数对。
/// </summary>
/// <param name="a">需要查找的数组。</param>
/// <returns></returns>
static int CountEqual(int[] a)
{
    var n = a.Length;
    var count = 0;
    for (var i = 0; i < n; i++)
    {
        for (var j = i + 1; j < n; j++)
        {
            if (a[i] == a[j])
                count++;
        }
    }

    return count;
}

/// <summary>
/// 利用 Array.Sort 进行优化的查找相等整数对算法。
/// </summary>
/// <param name="a">需要查找的数组。</param>
/// <returns></returns>
static int CountEqualLog(int[] a)
{
    var n = a.Length;
    var count = 0;
    Array.Sort(a);
    var dup = 0; // dup = 重复元素数量-1
    for (var i = 1; i < n; i++)
    {
        while (a[i - 1] == a[i])
        {
            dup++;
            i++;
        }
        count += dup * (dup + 1) / 2;
        dup = 0;
    }
    return count;
}