Сплит-массив + ve и -ve nums

Question

Я пытаюсь решить эту проблему для интервью. Я смог получить решение O (N) с пространственной полнотой O (N). Я пытаюсь выяснить, есть ли решение с O (1) пространство?

Вопрос:

Учитывая несортированный массив положительных и отрицательных чисел. Создайте массив альтернативных положительных и отрицательных чисел без, изменяя относительный порядок положительных и отрицательных чисел соответственно.

Входной сигнал:

Первая строка входного файла содержит целое число T, обозначающее количество тестов. Первая строка каждого тестового примера - N, N - размер массива. Вторая строка каждого тестового примера содержит N ввода a [].

Выход:

печати массив альтернативных положительных и отрицательных чисел. Примечание: Решение должно начинаться с положительного числа.

Ограничения:

1 ≤ T ≤ 30 1 ≤ N ≤ 100 -1000 ≤ в [] ≤ 1000

Пример:

Входной

1 
9 
9 4 -2 -1 5 0 -5 -3 2 

Выход

9 -2 4 -1 5 -5 0 -3 2 

.

import java.util.*; 
import java.lang.*; 
import java.io.*; 

class GFG { 
    public static void main (String[] args) { 
     //code 
     Scanner sn = new Scanner(System.in); 
     int T = sn.nextInt(); 
     for(int i=0; i<T; i++){ 
      int N = sn.nextInt(); 
      ArrayList<Integer> arr = new ArrayList<Integer>(); 
      ArrayList<Integer> pv_arr = new ArrayList<Integer>(); 
      ArrayList<Integer> ne_arr = new ArrayList<Integer>(); 
      for(int j=0; j<N; j++){ 
       int num = sn.nextInt(); 
       if(num<0){ 
        ne_arr.add(num); 
       }else{ 
        pv_arr.add(num); 
       } 
      } 

      int maxLen = Math.max(pv_arr.size(), ne_arr.size()); 
      for(int k = 0; k < maxLen; k++){ 
       if(k < pv_arr.size()){ 
       System.out.print(pv_arr.get(k) + " "); 
       } 
       if(k < ne_arr.size()){ 
       System.out.print(ne_arr.get(k) + " "); 
       } 
      } 
      System.out.println(" "); 
     } 
    } 
} 

Мой ответ создает два массива положительных & отрицательна и печатает их в качестве альтернативы. Я попытался использовать два указателя (один из положительных значений и один из отрицательных значений). Я не уверен, как решить это с помощью O (N) & O (1) пространства.

Answer 1

Если вы не напрямую получить массив в качестве входных данных для вашей функции, но вместо этого должны прочитать номера из стандартного входного потока означает, что вы должны будете создать массив себя. Кроме того, вопрос гласит:

Первая строка ... Вторая линия ...

это означает, что вход дается вам построчно, а не в качестве параметров функции.

Это будет означать, что лучшим решением является O (n) в терминах пространства.Вы уже нашли решение, которое работает, но вы все равно можете упростить его, используя подход «указатель», как вы сами сказали:

public static void main (String[] args) { 
    Scanner sn = new Scanner(System.in); 
    int T = sn.nextInt(); 
    for(int i=0; i<T; i++){ 
     int N = sn.nextInt(); 
     int[] numbers = new int[N]; 
     int neg_ind = 1; 
     int pos_ind = 0; 

     for(int j=0; j<N; j++){ 
      int num = sn.nextInt(); 
      if(num < 0){ 
       numbers[neg_ind] = num; 
       neg_ind += 2; 
      }else{ 
       numbers[pos_ind] = num; 
       pos_ind += 2; 
      } 
     } 

     System.out.println(Arrays.toString(numbers)); 
    } 
}