Wie kann ich dieses Programm in linearer Zeit ausführen?

Question

Also habe ich seit einigen Tagen an einer Aufgabenfrage gearbeitet und es ist mir extrem schwer gefallen, dieses Programm in linearer Zeit laufen zu lassen. Ich habe es in O (n^2) geschafft, aber ich möchte ein perfektes Ergebnis erzielen.

Hier ist die Frage: Wir werden gebeten, die Duplikate bestimmter Zahlen in negative zu ändern und dann alle Duplikate an das Ende des Arrays zu senden.

For example, if the input array is [ 4 , 1 , 1 , 3 , 3 , 3 , 1 , 1 ], it 
    reads [ 4 , 1 , 3 , 1 , -1 , -1 , -1 , -1 ] after squeeze() completes. 

Und hier ist mein Programm:

int base = ints[ints.length -1]; 
    int count = 0; 
    for (int i = ints.length - 1 ; i > 0 ; i--) 
    { 
     if (base == ints[i-1]) 
     { 
      ints[i] = N_ONE; 
      count++; 
     } else { 
      base = ints[i-1]; 
     } 
    } 
    int count2 = 0; 
    for (int j = 0; (count) != count2 ; j++) 
    { 
     if (ints[j] == -1 && ints[j+1] != -1) 
     { 
      ints[j] = ints[j+1]; 
      ints[j+1] = N_ONE; 
      count2 = 0; 
      j = 0; 
     } else if (ints[j] == -1 && ints[j+1] == -1){ 
      count2++; 
     } 
    } 
} 

Meine erste Schleife arbeitet effizient und es setzt alle Duplikate Zahlen als -1 ist jedoch nicht nur meine zweite Schleife nicht in linear-Laufzeit, aber ich fühle mich wie es einfacher gemacht werden kann. Ich habe versucht, die Prozesse von Hand zu schreiben, aber ich scheine immer noch nur Methoden zu finden, die O (n^2) sind.

Hat jemand Vorschläge oder Tipps? Gibt es etwas wirklich einfaches, was mir fehlt?

Vielen Dank im Voraus!

Answer 1

Das Konzept hinter dieser Lösung ist, wie ich in einem Kommentar vorgeschlagen: Machen Sie es in einem Durchgang, mit einem Index für jeden der Sie lesen und wo Sie schreiben. Schreiben Sie nur einmal, um einen Duplikatblock zu lesen. Wenn Sie keine Leseelemente mehr haben, füllen Sie einfach den Rest des Arrays mit -1.

Hier ist eine Implementierung, in Java. Wie Sie sehen können, habe ich nicht viel getestet.

import java.util.Arrays; 

public class Test { 
    public static void main(String[] args) { 
    testIt(new int[]{}); 
    testIt(new int[]{4, 1, 1, 3, 3, 3, 1, 1}); 
    testIt(new int[]{1}); 
    testIt(new int[]{1,1}); 
    testIt(new int[]{1,2}); 
    } 

    public static void testIt(int[] in) { 
    System.out.println(Arrays.toString(in)); 
    squeeze(in); 
    System.out.println(Arrays.toString(in)); 
    System.out.println(); 
    } 

    public static void squeeze(int[] data) { 
    int readIndex = 0; 
    int writeIndex = 0; 
    while(readIndex < data.length){ 
     if(readIndex == 0 || data[readIndex] != data[readIndex-1]){ 
     // Need to store this one 
     data[writeIndex] = data[readIndex]; 
     writeIndex++; 
     } 
     readIndex++; 
    } 
    while(writeIndex < data.length){ 
     data[writeIndex] = -1; 
     writeIndex++; 
    } 
    } 
}