Array-Codierungs-Herausforderung, die in O (n) -Komplexität gelöst werden muss

Question

Wir erhalten ein Array bestehend aus N Zahlen und einer Zahl X. Wir müssen einen Index K in diesem Array finden, der das Array in zwei Teile teilt (0 bis K-1 und K-1 bis N-1) als solche:

Anzahl der Elemente gleich X im ersten Teil = Anzahl der Elemente ungleich X im zweiten Teil.

Beispiel:

A = (5, 5, 1, 2, 3, 4, 5), X = 5 

Answer: K= 4 

(5, 5, 1, 2) contains two X's. 

(3, 4, 5) contains two non X's. 

Solche K existiert immer entsprechend der Problembeschreibung. Die Lösung muss eine O (N) -Komplexität aufweisen. O (N^2) Lösung ist zu einfach, aber ich konnte das O (N) nicht finden.

Hier ist, was ich bisher habe:

int function(int X, vector<int> &A) { 
    int k = 0; 
    vector<int> indices; 
    long count = A.size(); 
    int number_of_x= 0; 
    for(int i=0;i<count;i++){ 
     if(A[i]==X) 
      number_of_x++; 
    } 
    long part_one_x = 0; 
    long part_two_nonx = 0; 
    for(int i=0;i<count;i++){ 
     if(A[i]==X) 
      part_one_x++; 
     part_two_nonx = (count-i) - (number_of_x - part_one_x); 
     if(part_one_x == part_two_nonx) 
      k = i; 
    } 


    return k; 
} 

Vielen Dank für Ihre Hilfe!

Answer 1

Lassen Sie sich Ihr Beispiel betrachten ...

A = (5, 5, 1, 2, 3, 4, 5) 

Wenn Sie das erste Element betrachten - 5 - dann wissen wir jede Lösung einen nicht-5-Wert am anderen Ende haben muss, damit wir arbeiten nach hinten zu finden die erste nicht-fünf, die Verfolgung der „vorne“ und „hinten“ Orte, an arbeiten wir ...

A = (5, 5, 1, 2, 3, 4, 5) 
    ^   ^

so haben wir die 5s bisher mit dem nicht-5s als wir ausgewogen von den Enden her arbeiten. Jetzt schauen wir auf die nächste Position auf der linken Seite, der auch eine fünf, so bewegen wir die rechte Position links, bis wir eine andere Nicht-fünf finden:

A = (5, 5, 1, 2, 3, 4, 5) 
     ^ ^

Jetzt haben wir die linke Position vorrücken suchen für weitere fünf, aber treffen Sie die richtige Position, bevor Sie eine finden, also ist die "rechte Seite" eine Lösung.