+ veと-ve numの分割配列

Question

このインタビューの問題を解決しようとしています。私はO（N）空間の複雑さでO（N）解を得ることができました。私はO（1）スペースの解決策があるかどうかを調べようとしていますか？

質問：正と負の数の未ソート配列を指定して

。代替の正と負の数値の配列を作成し、を除いて、それぞれ正と負の相対的な順序を変更します。

入力：

入力の最初の行は、テストケースの数を表す整数値Tを含んでいます。 各テストケースの最初の行はN、Nは配列のサイズです。 各テストケースの2行目にはN入力a []が含まれています。

出力：

プリント代替の正および負の数のアレイ。 注：解決策は正の数で開始する必要があります。

制約：

1≤T≤30 1≤N []≤千

例≤100 -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）の空白でこれを解決する方法がわかりません2つのポインタ（正の値と負の値の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)); 
    } 
}