c - 大量输入的“因超时而终止”

Question

这个问题不适用于大量输入。

问题陈述

华生给夏洛克一个由 N 个整数 A0、A1 ... AN-1 组成的数组。现在 Watson 问 Sherlock 存在多少对不同的索引 i 和 j，使得 i 不等于 j 但 Ai 等于 Aj。

也就是说，Sherlock 必须计算索引对 (i, j) 的总数，其中 Ai = Aj AND i ≠ j。

输入格式第一行包含 T，测试用例的数量。 T 测试用例如下。每个测试用例由两行组成，第一行包含一个整数 N，数组的大小。下一行包含 N 个空格分隔的整数。

输出格式对于每个测试用例，在不同的行中打印所需的答案。

约束1≤T≤101 ≤ N ≤ 10^51 ≤ A[i] ≤ 10^6

示例输入

2

3

1 2 3

3

1 1 2

示例输出

0

2

解释在第一个测试用例中，不存在满足给定属性的两对索引。在第二个测试用例中 A[0] = A 1 = 1, 索引对 (0,1) 和 (1,0) 满足给定的性质。

代码

#include <stdio.h>
#include <string.h>
#include <math.h>
#include <stdlib.h>

int main() {
    long n,*a,i,j,count;
    int opt;
    scanf("%d",&opt);
    while(opt--)
        {
        count=0;
        scanf("%ld",&n);
        a=malloc(sizeof(long)*n);
        for(i=0;i<n;i++)
            scanf("%ld",&a[i]);
        for(i=0;i<n;i++)
            for(j=0;j<n;j++)
                if(a[i]==a[j]&& i!=j)
                    count++;

        printf("%ld\n",count);
    }
    /* Enter your code here. Read input from STDIN. Print output to STDOUT */    
    return 0;
}

注意:不适用于这些输入

Input

Output

Answer 1

您正在使用一种使用 O(N^2) 操作的算法。

我的建议:

1. 首先对数字进行排序。这将是一个 O(N*log(N)) 操作。
2. 然后，遍历排序后的列表。这将是一个线性的 O(N) 操作。

这就是我改变核心算法的方式:

qsort(a, n, sizeof(long), myCompare);

for(i=0;i<n;i++)
{
   for(j=i+1;j<n;j++)
   {
      if(a[i]==a[j])
      {
         count++;
      }
      else
      {
         i = j-1;
         break;
      }
   }
}

以及qsort使用的函数:

int myCompare(void* first, void* second)
{
   return (*(long*)first < (*(long*)second));
}