Java-Algorithmus: Segregate ungerade gerade Zahlen (Zeit-Raum-Komplexität)

Question

Ich schreibe eine Methode, die das Array von ganzen Zahlen trennt, so dass alle geraden ganzen Zahlen alle ungeraden Ganzzahlen im Array vorausgehen. Es muss lineare Zeit in der Größe des Arrays O(n) nehmen und an Ort und Stelle mit nur einer konstanten Menge an zusätzlichem Platz arbeiten.

Input: {2, 4, 7, 6, 1, 3, 5, 4}
Output: 2, 4, 6, 4, 7, 1, 3, 5

Input: {5 , 12, 3, 21, 8, 7, 19, 102, 201}
Output: 12, 8, 102, 5, 3, 21, 7, 19, 201

Dies waren meine Lösungen:

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

Methode 1 benötigt O (n) und benötigt keinen zusätzlichen Platz. Es hält jedoch nicht die Ordnung aufrecht.

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

Methode 2 erstellt ArrayList. Ich bin mir nicht sicher, ob das auch O (n) ist.

Zum Test:

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

Ich bin nicht sicher, ob es eine sauberere Lösung/Einfachheit ist die Raum-Zeit-Komplexität (O (n) und Raumbegrenzung) erfüllt.

Answer 1

Der einfachste Weg, dies zu tun und die gleiche Zeit Komplexität zu halten und auch, dass die Größe des Ausgangsarrays die gleiche Größe wie das Eingangsarray hat, ist eine Modulo-Prüfung für jeden Wert und wenn es positiv platziert ist an der Vorderseite des Arrays und wenn negativ, dann nach hinten. Bitte beachten Sie, dass Sie zwei Variablen benötigt, um den nächsten verfügbaren Stellen für die positive und negative Zahlen kennen