降低以下程序的时间复杂度 [英] Reduce Time complexity of the following program

问题描述

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);
    }       
}
}

帮助我降低这个程序的时间复杂度

你得到了一个大小为 N 的整数数组 A.你必须报告有序对的数量 (i,j) 使得 A[i] &A[j]=0.这里 & 表示 BITWISE AND (i,j) 和 (j,i) 被认为是不同的.

You have been given an integer array A on size N. You must report the number of ordered pairs (i,j) such that A[i] & A[j]=0. Here & denotes the BITWISE AND (i,j) and (j,i) are considered different.

输入:第一行包含测试用例的 T 数.每个测试的第一行包含 N.下一行包含 N 个整数 - 第 i 个整数 A[i].

Input: First line contains T-Number of Test cases. First line of each test contains N. Next line contains N integers - the i'th integer A[i].

输出:输出每个测试用例的此类对的数量.

Output: Output the number of such pairs for each test case.

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

Constraints: T ≤ 10; N ≤ 100000; A[i] ≤ 1000000

样本输入(明文链接)

<代码>1541 47 34 40 29

样本输出(明文链接)

2

说明:这些是必需的对 (3 5) (5 3)

推荐答案

我会为此提出三个优化建议.我也修改了代码.

I would suggest three optimization for this. I have modified the code as well.

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

1. You need not to always start from 0 for each iteration of outer loop. The second loop can start from current+1 of the first loop. So will not be comparing elements which you have already compared.
2. You don't need to check for both pairs (i,j) and (j,i). If one is zero then other will always be zero.
3. You need not to initialize the array with fix size. You can always initialize it reading the value of 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);
    }
  }
}

这篇关于降低以下程序的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！