1.4.8

上次更新:2019-04-17
发现了题解错误/代码缺陷/排版问题?请点这里:如何:提交反馈

解答

平方级别:直接二层循环遍历一遍。
线性对数:
先对数组排序,然后遍历一遍数组,在遍历过程中计算重复元素的数量,
然后用公式 $ 1+2+\cdots+n-1=n(n-1)/2 $ 计算重复整数对的数量。

代码

/// <summary>
/// 暴力查找数组中相等的整数对。
/// </summary>
/// <param name="a">需要查找的数组。</param>
/// <returns></returns>
static int CountEqual(int[] a)
{
    int n = a.Length;
    int count = 0;
    for (int i = 0; i < n; i++)
    {
        for (int 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)
{
    int n = a.Length;
    int count = 0;
    Array.Sort(a);
    int dup = 0; // dup = 重复元素数量-1
    for (int i = 1; i < n; i++)
    {
        while (a[i - 1] == a[i])
        {
            dup++;
            i++;
        }
        count += dup * (dup + 1) / 2;
        dup = 0;
    }
    return count;
}
上一题 下一题