我必须找到给定数除数的偶数。为此，我尝试了。我得到了正确的输出，但是我得到的时间复杂度超过了要求。问题：-第一行包含测试用例T的数量，其后T行分别包含一个整数N输出应该是-对于每个测试用例，打印只需一行即可获得所需答案。如何降低此给定代码的复杂度？或者有人可以建议更有效的方法...
import java.io.BufferedReader;
import java.io.InputStreamReader;
public class TestClass {
public static void main(String args[]) throws Exception {
// Read input from stdin and provide input before running
String frt = "";
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String line = br.readLine();
int T = Integer.parseInt(line);
int[] inp = new int[T];
for (int i = 0; i < T; i++) {
int x = Integer.parseInt(br.readLine());
inp[i] = x;
}
int[] ans = new int[T];
int count = 1;
for (int i = 0; i < T; i++) {
int x = inp[i];
if (x % 2 == 0) {
for (int j = 2; j <= x / 2; j = j + 2) {
if (x % j == 0)
count++;
}
} else
count = 0;
ans[i] = count;
}
for (int i = 0; i < T; i++)
System.out.println(ans[i]);
}
}
最佳答案
import java.io.*;
class Ideone
{
public static void main (String[] args) throws Exception
{
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int T = Integer.parseInt(br.readLine());
int i,j,k,n;
int[] inp = new int[T];
for (i = 0; i < T; i++) {
inp[i] = Integer.parseInt(br.readLine());
}
//Find all the primes numbers till the square-root of 10^9.
int MAX, root, arrLen;
MAX=1000000000;
arrLen=(int)Math.sqrt(MAX); // arrLen=31622
boolean[] primes=new boolean[arrLen+2]; // No need to find all the primes numbers till MAX
primes[0]=primes[1]=false;
for(i=2;i<arrLen;i++)
primes[i]=true;
// Using Sieve of Eratosthenes
// Square root of 31622 is 177.8
root=(int)Math.sqrt(arrLen); // root=177
for(i=2;i<=root;i++)
{
if(primes[i])
{
n=i*i;
k=0;
//arrLen is the length of primes array.
for(j=n; j<arrLen; k+=1, j=n+(i*k))
primes[j]=false;
}
}
int[] ans = new int[T];
for( i = 0; i < T; i++) {
n = inp[i];
if(n%2==1)
{
ans[i]=0; // Odd numbers will have 0 even divisors
}
else
{
int[] facts=new int[50];
for(k=0;k<50;k++)
facts[k]=1;
facts[0]=0; // fact[0] will contain the highest power of 2 that divides n.
while(n%2==0)
{
facts[0]+=1;
n=n/2;
}
// Prime factorizing n
j=1;
for( k=3; k<arrLen; k+=2)
{
if(primes[k] && n%k==0)
{
while(n%k==0)
{
facts[j]+=1;
n=n/k;
}
j+=1;
}
if(n==1) // To check if n has been completely divided or not.
break;
}
if(n!=1) // To check if there is any prime factor greater than the square root of MAX.
{
facts[j]+=1;
j+=1;
}
int count=1;
for(k=0;k<j;k++)
count=count*facts[k];
ans[i]=count;
}
}
for ( i = 0; i < T; i++)
System.out.println(ans[i]);
}
}
我觉得这个问题可能已经发布在任何竞争性编码平台上，可能像HackerEarth一样。如果是这样，那么请不要在StackOverFlow上发布直接问题（我认为）。
无论如何，我已经测试了我的代码，它可以正确运行。
在无法减少时间复杂度的问题中，首先请确保未创建不必要的对象。在内存中创建对象是一项耗时的操作。避免不相关地创建对象和变量。上面的代码仍然可以优化，但这会降低其可读性。 :)
同样在解决问题之前，请尝试找出各种测试用例。像奇数将有0个偶数除数。因此通过检查一个数字是否为奇数，可以减少几个运算。
上面的代码有更多解释：
一个数字的除数的数量为：（N1 + 1）（N2 + 1）（N3 + 1）...。其中N1，N2，N3等是该数字的质数的幂。
现在，如果N1是2（唯一的偶数），
那么数字的偶数除数是：N1 *（N2 + 1）*（N3 + 1）...
在事实[]数组中，事实[0]对应于N1，而N2，N3等存储在事实[1]，事实[2]等中。
facts [0]初始化为0，而其他初始化为1。
该计数存储最终乘积：N1 *（N2 + 1）*（N3 + 1）...，它等于原始数的偶数除数。