Java Permutation Challenge - Slow

Question

Я работаю над проблемой перестановки из GeeksforGeeks. Вот ссылка на вызов: http://www.practice.geeksforgeeks.org/problem-page.php?pid=702

Задача состоит в том, чтобы взять массив чисел и для каждого возможного порядка этих чисел в группах по 2 или 3, проверить, делится ли сумма чисел на 3. На конец программы распечатать число групп, которые делятся на 3.

примером может быть ... INT [] массив = {1, 2, 3} должен распечатать 8.

Ниже приведен код, который я использовал для этой задачи. Код работает, но он замедляется. Время выполнения должно быть ниже 1.272, так как я могу сделать этот код быстрее? Или сохранить его от выполнения так много строк?

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

Вот счетчик класса:

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

Ваш код создает много ненужных объектов.

Во-первых, класс счетчика не нужен, вы можете просто просто сохранить счетчик int числа групп, соответствующих требованию.

При расчете, если сумма делится на 3 вам не нужно идти через цифру, просто проверить (для Int n): if (n % 3 == 0) { ...

Вы создаете строки, а затем преобразования Интсов в строки и обратно снова излишне. Просто прочитайте int из командной строки в массив int и используйте это.

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

Наконец, рекурсия будет медленнее, чем простая итерация цикла. Я лично не считаю, что рекурсия делает решение более чистым.

Я бросил вместе быстрое наивное решение с этими предложениями, и это заняло всего около 1/2 секунды для запуска.