Java 排列挑战是慢

Question

我一直在研究 GeeksforGeeks 的排列问题。这是挑战的 link：http://www.practice.geeksforgeeks.org/problem-page.php?pid=702

挑战是获取一个数字数组，并针对这些数字以 2 或 3 为一组的每个可能顺序，检查数字之和是否可以被 3 整除。在程序结束时打印出可被 3 整除的组数。

一个例子是... int[] array = {1, 2, 3} 应该打印出 8。

以下是我用于此挑战的代码。该代码有效，但速度很慢。运行时需要低于 1.272s 那么我怎样才能使这段代码更快？还是省去执行这么多行？

  public static void PG2(int[] array, int l, int r, Counter count){
        int newR = r - 1;
        int i;
       if(l == 2){
           String number = String.valueOf(array[0]);
           String number2 = String.valueOf(array[1]);
           number = number.concat(number2);
           int aNumber = Integer.parseInt(number);
           count.divBy3(aNumber);
       } else {
            int temp;
            int temp2;
            for(i = l; i < r; i++){
                temp = array[l];
                array[l] = array[i];
                array[i] = temp;
                PG2(array, l+1, r, count);
                temp2 = array[l];
                array[l] = array[i];
                array[i] = temp2;
            }
        }   
    }

    public static void PG3(int[] array, int l, int r, Counter count){
        int newR = r - 1;
        int i;
       if(l == 3){
           String number = String.valueOf(array[0]);
           String number2 = String.valueOf(array[1]);
           String number3 = String.valueOf(array[2]);
           number = number.concat(number2);
           number = number.concat(number3);
           int aNumber = Integer.parseInt(number);
           count.divBy3(aNumber);
       } else {
            int temp;
            int temp2;
            for(i = l; i < r; i++){
                temp = array[l];
                array[l] = array[i];
                array[i] = temp;
                PG3(array, l+1, r, count);
                temp2 = array[l];
                array[l] = array[i];
                array[i] = temp2;
            }
        }   
    }




    public static void main(String[] args) throws Exception {
        BufferedReader input = new BufferedReader(new InputStreamReader(System.in));

        String t = input.readLine();
        int T = Integer.parseInt(t);

        while(T > 0){
            String arrayS = input.readLine();
            int ArrayS = Integer.parseInt(arrayS);

            int[] newArray = new int[ArrayS];

            String arrayElements = input.readLine();
            String[] ArrayElements = arrayElements.trim().split("\s+");
            for(int i = 0; i < ArrayS; i++){
                int num = Integer.parseInt(ArrayElements[i]);
                newArray[i] = num;
            }
            int total = 0;
            Counter count = new Counter();
            PG2(newArray, 0, ArrayS, count);
            PG3(newArray, 0, ArrayS, count);

            System.out.println(count.counter);
            T--;
        }
    }

这是计数器class:

public class Counter {
    public int counter;

    public void divBy3(int number){
        int total = 0;
        while(number > 0){
            total += number % 10;
            number = number / 10;
        }

        if(total % 3 == 0){
            this.counter++;
        }
    }


}

Answer 1

您的代码创建了很多不必要的对象。

首先，不需要计数器 class，您可以轻松地保留一个符合要求的组数的整数计数器。

当计算一个总和是否可以被 3 整除时，你不需要遍历数字，只需检查（对于 int n）：if (n % 3 == 0) { ...

您正在创建字符串，然后将整数转换为字符串，然后再不必要地返回。只需将命令行中的整数读入一个整数数组并使用它。

// a main method that reads in ints and then keeps them as such
Scanner in = new Scanner(System.in);
int t = in.nextInt();
while (t > 0) {
    int n = in.nextInt();
    int[] arr = new int[n];
    for (int i = 0; i < n; i++) {
        arr[i] = in.nextInt();
    }
    int count = countGroupsOfTwo(arr);
    count += countGroupsOfThree(arr);
    System.out.println(count);
    t--;
}

最后，递归将比简单的 for 循环迭代慢。我个人也不认为递归使解决方案更清晰。

我根据这些建议拼凑了一个简单的快速解决方案，运行只花了大约 1/2 秒。

Java 排列挑战是慢

Java Permutation Challenge is to Slow

java

recursion

runtime

permutation