Sagen Sie, ich habe die folgende Zahlenliste:
%Vor%Ich möchte jedes geschlossene Intervall finden, das aufeinanderfolgende ganze Zahlen ohne Lücken in dieser Liste enthält. Wenn für eine Zahl in der Liste mehrere solcher Intervalle vorhanden sind, behalten wir nur die größten von solchen Intervallen bei. Die richtige Antwort oben sollte lauten:
%Vor%Um dies zu sehen, beachten Sie zum Beispiel:
Das geschlossene Intervall [0,0] enthält die Ganzzahl 0 , enthält keine Lücken und keines seiner Elemente ist in einem anderen geschlossenen Intervall enthalten.
Das geschlossene Intervall [3,4] enthält keine Lücken und seine Elemente sind in keinem anderen geschlossenen Intervall enthalten, das keine Lücken aufweist, die größer sind als sich selbst.
Wie kann ich das in wenigen Worten tun? Ich fing an, einen Algorithmus zu schreiben, der np.diff(my_array) verwendet, um Übergänge im Array zu erkennen, aber es scheitert an Eckfällen wie Intervallen, die nur ein Element enthalten.
Ich habe kein numply install handlich, aber das ist der Ansatz, den ich nehmen würde. Behandeln Sie zuerst den Fall eines leeren Arrays separat. Sortieren Sie das Array, wenn es nicht bereits sortiert ist, und verwenden Sie np.diff , um die Unterschiede zu berechnen.
Teste die Unterschiede, um > 1 zu sein.
Um den Anfang der Intervalle zu erhalten, geben Sie am Anfang ein 1 ein und wählen Sie die entsprechenden Array-Elemente aus. Um die Enden zu erhalten, setzen Sie am Ende ein 1 und wählen Sie die entsprechenden Array-Elemente.
Implementierung (weitgehend von user815423426):
%Vor%