Javaアルゴリズム：奇数偶数を分離する（時間空間の複雑さ）

Question

すべての偶数が配列内のすべての奇数の前にくるように整数の配列を分離するメソッドを書いています。それは配列O(n)のサイズの線形時間を取らなければならず、余分なスペースの一定量だけで動作します。

入力：{2、4、7、6、1、3、5、4}
出力：2、4、6、4、7、1、3、5

入力：{5 、12、3、21、8、7、19、102、201}
出力：12、8、102、5、3、21、7、19、201

これらは私の溶液であった：

private static void segregateArray1(final int[] arr) { 
    if (arr != null) { 
     int leftIdx = 0; 
     int rightIdx = arr.length - 1; 

     while (leftIdx < rightIdx) { 
      if (arr[leftIdx] % 2 != 0 && arr[rightIdx] % 2 == 0) { 
       // swap immediately 
       int temp = arr[leftIdx]; 
       arr[leftIdx] = arr[rightIdx]; 
       arr[rightIdx] = temp; 
       leftIdx++; 
       rightIdx--; 
      } else { 
       if (arr[leftIdx] % 2 == 0) { 
        leftIdx++; 
       } 
       if (arr[rightIdx] % 2 == 1) { 
        rightIdx--; 
       } 
      } 
     } 
    } 
} 

方法1はO（n）をとり、余分なスペースを消費しません。ただし、注文は維持されません。

private static int[] segregateArray2(final int[] arr) { 
    List<Integer> evenArr = new ArrayList<Integer>(); 
    List<Integer> oddArr = new ArrayList<Integer>(); 

    for (int i : arr) { 
     if (i % 2 == 0) { 
      evenArr.add(i); 
     } else { 
      oddArr.add(i); 
     } 
    } 
    evenArr.addAll(oddArr); 

    return ArrayUtils.toPrimitive(evenArr.toArray(new Integer[0])); 
} 

メソッド2は、ArrayListを作成します。これもO（n）であるかどうかはわかりません。テストへ

：

public static void main(String[] args) { 
    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4}; 
    segregateArray1(arr); 
    System.out.println(Arrays.toString(arr)); 

    int[] arr = {2, 4, 7, 6, 1, 3, 5, 4}; 
    // creates another array segragatedArr! 
    int[] segragatedArr = segregateArray2(arr); 
    System.out.println(Arrays.toString(segragatedArr)); 
} 

私は時空間複雑さ（O（n）とスペースの制約）を満たすすっきりソリューション/シンプルがあるかどうかわかりません。

Answer 1

これを実行して同じ時間の複雑さを維持する最も簡単な方法、および出力配列のサイズが入力配列と同じサイズで、各値のモジュラスチェックを行い、アレイの前面に、負の場合は背面に移動します。正と負の数字の次の使用可能な場所を知るには、2つの変数が必要です。