Java的算法：·隔離奇數偶數（時間和空間複雜度）

我寫偏析整數數組的方法，使所有的偶數先於陣列中的所有奇數。它必須在數組O(n)的線性時間內運行，並且只有恆定的額外空間才能運行。Java的算法：·隔離奇數偶數（時間和空間複雜度）

輸入：{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）和空間的限制）。

來源

2016-04-25 sophie

做到這一點，保持相同的時間複雜度和最簡單的方法也使輸出數組的大小是作爲輸入陣列是做在每個值的模數校驗相同的尺寸和放置，如果它是正的，以到陣列的前面，如果是負向的話，則返回到後面。請記住，你將需要兩個變量知道爲正數和負數下一個可用的位置

來源

2016-04-25 14:27:01 Shon

Java的算法：·隔離奇數偶數（時間和空間複雜度）

回答

相關問題