降低以下程序的时间复杂度

Question

import java.util.Scanner;
class Special_Pairs{

private static Scanner scan;


public static void main(String [] args) {
    byte t;
    int n;
    scan = new Scanner(System.in);
    t=scan.nextByte();
    int[] a=new int[100000];
    while(t>0)
    {
        int i,j,count=0;
        n=scan.nextInt();
    for(i=0;i<n;i++)
    {
        a[i]=scan.nextInt();
    }
    for(i=0;i<n;i++)
    {
        for(j=0;j<n;j++)
        {
            if(((a[i]&a[j])==0)||((a[j]&a[i])==0))
            {
                count++;
            }
        }
    }
    t--;
    System.out.println(count);
    }       
}
}

帮助我减少这个程序的时间复杂性

输出：为每个测试用例输出这样的对的数量。

约束条件:T≤10；N≤100000；A[i]≤1000000

示例输入（明文链接）

Answer 1

我建议对此进行三个优化。我也修改了代码。

1. 对于外循环的每次迭代，不必总是从0开始。第二个循环可以从第一个循环的current+1开始。因此不会比较您已经比较过的元素。
2. 您不需要同时检查(i,j)和(j,i)对。如果一个为零，则另一个将始终为零。
3. 您不需要用固定大小初始化数组。您可以始终读取n的值来初始化它。

import java.util.Scanner;

public class Pairs {
  public static void main(String [] args) {
    Scanner scan = new Scanner(System.in);
    int t = scan.nextInt();
    while(t > 0) {
      t--;
      int count = 0;
      int n = scan.nextInt();
      int a[] = new int[n];
      for(int i = 0; i<n; i++) {
        a[i]=scan.nextInt();
      }
      for(int i = 0; i<n-1; i++) {
        for(int j = i+1; j<n; j++) {
          if((a[i] & a[j])==0)
          {
            count += 2;
          }
        }
      }
      System.out.println(count);
    }
  }
}