计算在高效算法中选择两个数字的方式数

Question

我解决了这个问题,但我在网上判断时超过 TLE 时间限制

程序的输出是正确的,但我认为可以提高方式,以提高效率!

问题 :

给定n整数,计算我们可以选择两个元素的方式的数量,使得它们的绝对差值小于32.

以更正式的方式,计算(i, j) (1 ? i < j ? n)这样的对数

|V[i] - V[j]| < 32.|X| 是绝对值X.

输入

第一行输入包含一个整数T,即测试用例的数量(1 ? T ? 128).

每个测试用例都以整数开头n (1 ? n ? 10,000).

下一行包含n整数(1 ? V[i] ? 10,000).

产量

对于每个测试用例,在一行上打印对数.

我在c ++中的代码:

int main() {
    int T,n,i,j,k,count;
    int a[10000];
    cin>>T;

for(k=0;k<T;k++)
 {   count=0;
     cin>>n;
    for(i=0;i<n;i++)
    {
      cin>>a[i];
    }
    for(i=0;i<n;i++)
    {
        for(j=i;j<n;j++)
        {
          if(i!=j)
          {
            if(abs(a[i]-a[j])<32)
                count++;
          }
        }
    }
    cout<<count<<endl;
 }
    return 0;
}

我需要帮助如何在更有效的算法中解决它？

Answer 1

尽管我之前(愚蠢)回答,但根本不需要对数据进行排序.相反,你应该计算数字的频率.

然后,您需要做的就是跟踪要配对的可行数的数量,同时迭代可能的值.抱歉没有c ++,但java也应该是可读的:

int solve (int[] numbers) {                                                 
    int[] frequencies = new int[10001];                                     
    for (int i : numbers) frequencies[i]++;                                 
    int solution = 0;                                                       
    int inRange = 0;                                                        
    for (int i = 0; i < frequencies.length; i++) {                          
        if (i > 32) inRange -= frequencies[i - 32];                         
        solution += frequencies[i] * inRange;                               
        solution += frequencies[i] * (frequencies[i] - 1) / 2;              
        inRange += frequencies[i];                                           
    }                                                                        
    return solution;                                                         
}