-4

Please can any one provide with a better algorithm then trying all the combinations for this problem.

Given an array A of N numbers, find the number of distinct pairs (i, j) such that j >=i and A[i] = A[j].

First line of the input contains number of test cases T. Each test case has two lines, first line is the number N, followed by a line consisting of N integers which are the elements of array A.

For each test case print the number of distinct pairs.

Constraints: 1 <= T <= 10
1 <= N <= 10^6
-10^6 <= A[i] <= 10^6 for 0 <= i < N

I think that first sorting the array then finding frequency of every distinct integer and then adding nC2 of all the frequencies plus adding the length of the string at last. But unfortunately it gives wrong ans for some cases which are not known help. here is the implementation.

code:
#include <iostream>
#include<cstdio>
#include<algorithm>
using namespace std;

long fun(long a) //to find the aC2 for given a
{
    if (a == 1) return 0;
    return (a * (a - 1)) / 2;
}

int main()
{
    long t, i, j, n, tmp = 0;
    long long count;
    long ar[1000000];
    cin >> t;

    while (t--)
    {
        cin >> n;
        for (i = 0; i < n; i++)
        {
            cin >> ar[i];
        }
        count = 0;
        sort(ar, ar + n);

        for (i = 0; i < n - 1; i++)
        {
            if (ar[i] == ar[i + 1])
            {
                tmp++;
            }
            else
            {
                count += fun(tmp + 1);
                tmp = 0;
            }
        }

        if (tmp != 0)
        {
            count += fun(tmp + 1);
        }
        cout << count + n << "\n";

    }
    return 0;
}
4

1 回答 1

2

记录每个数字在数组中出现的次数。然后遍历结果数组并为每个数组添加三角数。

例如（来自源测试用例）：

Input:
3
1 2 1

count array = {0, 2, 1} // no zeroes, two ones, one two
pairs = triangle(0) + triangle(2) + triangle(1)
pairs = 0 + 3 + 1
pairs = 4

三角形数可以通过 计算(n * n + n) / 2，整个过程是 O(n)。

编辑：

首先，如果您计算频率，则无需排序。我看到你对排序做了什么，但如果你只保留一个单独的频率数组，那就更容易了。它需要更多空间，但由于元素和数组长度都被限制为< 10^6，因此您需要的最大值是int[10^6]. 这很容易满足挑战中给出的 256MB 空间要求。（哎呀，因为元素可以为负数，所以你需要一个两倍大小的数组。不过仍然远低于限制）

对于这n choose 2部分，你错的部分是它是一个n+1 choose 2问题。由于您可以单独配对每个，因此您必须将一个添加到n. 我知道你n在最后添加，但它不一样。tri(n)和之间的区别tri(n+1)不是一个，而是n。

于 2013-10-02T14:54:29.340 回答