java - 检查图是否存在(java)

Question

确定是否存在具有一系列顶点度数的图 (s = s1, s2...sn)。解决这个问题最好、最优化的算法是什么。

 Input:
    the first line contains `t<100` - amount of sequnces.
    the second line contains value `n <= 1000000`(length of a sequence).
    the third line contains  contains `n` non-negative integer numbers. And so on.
Output:
    if the graph can exist print "yes" otherwise print "no".
For example: 
Input:
3
5
1 2 3 2 1
4
3 3 2 2
3
1 3 2
Output:
No
Yes
Yes

最大执行时间应为 0.4 秒。这是我的代码(如果奇数顶点的数量是偶数，则图存在):

    import java.util.Scanner;
public class Main {
      public static final Scanner in = new Scanner(System.in);
    public static void isGraph (int []a, int n) {
        int k=0;
        for(int i=0; i< n; i++) {
            if(a[i] %2 != 0) {
                k++;
            }
        }
        if(k%2 == 0)
           System.out.println("Yes");
        else
            System.out.println("No");

    }
    public static void main(String[] args) throws Exception{
        double t1 = System.nanoTime();
        int n;
        int []a;
        int t = Integer.parseInt(in.nextLine());
        while(t-- > 0) {
            n = in.nextInt();
            a = new int[n];
            for(int i=0; i<n; i++)
                a[i] = in.nextInt();
            isGraph(a,n);
        }
        System.out.println(System.nanoTime() - t1);
    }
}

但是这个程序的执行时间超过了0.4秒。我的运行时间超出了。我如何优化代码并加快运行时间。可能有另一种算法可以解决这个任务，请帮助我。

Answer 1

我想我有一个更快的方法给你。请确认这一点。如果您关心偶数/奇数的最终结果，那么似乎没有理由跟踪 k 计数器。您可以保留运行顺序是偶数还是奇数的动态值:

public static void isGraph (int []a, int n) {
    int k = 0;
    for(int i=0; i< n; i++) {
        k += a[i] & 1;
    }
    if(k%2 == 0)
        System.out.println("Yes");
    else
        System.out.println("No");

}

这可能对您的阅读有所帮助:我对此没有经验，但是，我从竞赛网站获得了它:

缓慢的阅读方式:

/** Read count integers using Scanner */
static int scanInteger(int count) {
    Scanner scanner = new Scanner(input);
    int last = 0;
    while (count-- > 0) {
        last = scanner.nextInt();
    }
    return last;
 }

更快的方法:

static int readIntegers(int count) 
    throws IOException {
    BufferedReader reader = new BufferedReader(
           new InputStreamReader(input) );
    StringTokenizer tokenizer = new StringTokenizer("");
    int last = 0;
    while (count-- > 0) {
        if (! tokenizer.hasMoreTokens() ) {
            tokenizer = new StringTokenizer(reader.readLine());
        }
        last = Integer.parseInt(tokenizer.nextToken());
    }
    return last;
}

编辑:展示如何避免两个阶段，其中阶段 1 是读取循环，阶段 2 是算法:

public static void main(String[] args) throws Exception{
    double t1 = System.nanoTime();
    int n;
    // int []a;  //  Not necessary
    int t = Integer.parseInt(in.nextLine());
    while(t-- > 0) {
        n = in.nextInt();
        // a = new int[n];  // Not necessary
        int k = 0;
        int a;
        for(int i=0; i<n; i++) {
            a = in.nextInt();
            k += a & 1;
        }
        // isGraph(a,n);  // Not necessary
        if(k % 2 == 0)
            System.out.println("Yes");
        else
            System.out.println("No");
    }
    System.out.println(System.nanoTime() - t1);
}