Ich habe einen Test in C ++ gemacht, der nach einer Funktion fragt, die einen der Indizes zurückgibt, der den Eingabevektor in zwei Teile teilt, die die gleiche Summe der Elemente haben, zB: für vec = {1, 2, 3, 5, 4, -1, 1, 1, 2, -1} , kann er 3 zurückgeben, weil 1 + 2 + 3 = 6 = 4-1 + 1 + 1 + 2-1. Also habe ich die Funktion gemacht, die die richtige Antwort zurückgibt:
Mein Problem war, wenn die Eingabe ein sehr langer Vektor war, der nur 1 (oder -1) enthielt, war die Rückgabe der Funktion langsam. Also habe ich daran gedacht, die Suche nach dem gewünschten Index von der Mitte aus zu starten und dann nach links und rechts zu gehen. Aber der beste Ansatz ist der, bei dem der Index in der Sortierreihenfolge des Merge-Sorts liegt, also n / 2, n / 4, 3n / 4, n / 8, 3n / 8, 5n / 8, 7n / 8 ... wobei n die Größe des Vektors ist. Gibt es eine Möglichkeit, diese Reihenfolge in einer Formel zu schreiben, damit ich sie in meiner Funktion anwenden kann?
Danke
BEARBEITEN Nach einigen Kommentaren muss ich erwähnen, dass ich den Test vor ein paar Tagen gemacht habe, also habe ich vergessen den Teil von no solution zu setzen und zu erwähnen: es sollte -1 zurückgeben ... Ich habe auch den Fragetitel aktualisiert.
Speziell für dieses Problem würde ich den folgenden Algorithmus verwenden:
Dies ergibt einen o (n) Algorithmus anstelle von o (n2)
Sie können das Problem viel schneller lösen, ohne std::accumulator bei jedem Schritt aufzurufen:
Das ist O(n) . Bei jedem Schritt enthält s1 die Summe der ersten p -Elemente und s2 die Summe des Rests. Sie können beide mit einem Zusatz und einer Subtraktion aktualisieren, wenn Sie zum nächsten Element wechseln.
Da std::accumulator über den Bereich, den Sie ihm geben, iterieren muss, war Ihr Algorithmus O(n^2) , weshalb er für viele Elemente so langsam war.
Um die Frage zu beantworten: Ihre Sequenz n / 2, n / 4, 3n / 5, n / 8, 3n / 8 kann als
umgeschrieben werden %Vor%Das heißt, der Nenner läuft von i = 2 nach oben in Potenzen von 2, und der Nenner läuft von j = 1 bis i-1 in 2er Schritten. Dies ist jedoch nicht das, was Sie für Ihr tatsächliches Problem brauchen , weil das Beispiel, das du gibst, n = 10 hat. Offensichtlich wollen Sie dort nicht n / 4 - Ihre Indizes müssen Integer sein.
Die beste Lösung ist hier zu rekrutieren. Bei einem Bereich [b, e] wählen Sie einen Wert in der Mitte (b + e / 2) und setzen Sie die neuen Bereiche auf [b, (b + e / 2) -1] und [(b + e / 2) = 1 , e]. Natürlich spezialisieren Sie Bereiche mit der Länge 1 oder 2.
Angesichts der Kommentare von MSalters befürchte ich, dass eine andere Lösung besser wäre. Wenn Sie weniger Speicher verwenden möchten, ist die ausgewählte Antwort möglicherweise gut genug, aber um die möglicherweise mehrere Lösungen zu finden, können Sie den folgenden Code verwenden:
%Vor%Auf diese Weise erhalten Sie alle möglichen Lösungen. Wenn es keine Lösung gibt, den Vektor in zwei gleiche Hälften zu teilen, wird mid_indices leer gelassen. Auch hier müssen Sie jeden Wert nur einmal zusammenfassen.
Mein Vorschlag ist dies:
Es fügt jeden Wert nur einmal hinzu, unabhängig von der Anzahl der Werte. Solch eine Komplexität ist nur O (n) und nicht O (n ^ 2).
Der Code läuft simultan von links nach rechts und bewegt die Indizes weiter, wenn die Seite niedriger ist als die andere.
Hier ist der Algorithmus in Javascript:
%Vor%}
Wie Sie sehen, erfüllt dieser Code die Bedingung von O (n)