Erstellen Sie Intervalle in einem sortierten Array

Question

Nehmen wir an, ich habe ein sortiertes Array von {1, 2, 3, 4, 5, 7, 8, 9, 10, 15, 16, 21, 23, 25, 26}. Ich möchte diese Elemente in Abständen die folgende Art und Weise setzen:

1..5 
7..10 
15..16 
21..21 
23..23 
25..26 

In Wirklichkeit ich viel größere Daten haben, so würde ich einen Algorithmus mit einer guten Laufzeit benötigen.

Was ich im Sinn hatte, ist folgendes: Trennen Sie das Array in 2 Teile und mit 4 Schleifen durch das Array. Eine Schleife von 0 Index, 2 Schleife von der Mitte des Arrays und 1 Schleife vom Ende davon. Jede Schleife würde prüfen, ob das aktuelle und das nächste Element diff 1 ist, wenn ja, dann gehe zum nächsten Element, andernfalls erzeuge ein Intervall von vorherigen Elementen und starte ein neues Intervall vom nächsten Element.

Meine Frage ist, dass es ein guter Ansatz ist, oder gibt es einen besseren Weg? Bitte Pseudo- oder Java-Code.

Answer 1

Linear Lösung:

int intervalStart = a[0]; 
for (int i = 1; i < a.length; ++i) { 
    if (a[i] > a[i-1] + 1) { 
     outputInterval(intervalStart, a[i-1]); 
     intervalStart = a[i]; 
    } 
} 
outputInterval(intervalStart, a[a.length-1]); 

Runnable Version: https://ideone.com/NZ2Uex

Answer 2

könnten Sie betrachten eine Reihe von IntRange s von Apache Commons mit einem solchen Konzept darzustellen.

Ja, es erfordert eine 3rd-Party-Bibliothek, aber es ist schließlich Apache Commons.

Answer 3

Sie versuchen, die Listen aufeinanderfolgender Ganzzahlen zu erhalten.

Die einfachste und naive Art und Weise in O (n) ist, so etwas zu tun:

List<List<Integer>> list_of_sublists = new List<>(); // The list of sublists 
int lastElement = elements[0]; 
List<Integer> subList = new List <>(); // The current sublist 
subList.add(lastElement); 
int i = 1; // We start with index 1 because index 0 is already done 
while (i < elements.length){ 
    int element = elements[i] 
    if !(lastElement + 1 == element)){ //If not a consecutive we start a new list 
     list_of_sublists.add(subList); 
     subList = new List<>(); 
    } 
    lastElement = element; 
    subList.add(element); 
    i ++; 

//We didn't add the last sublist 
list_of_sublists.add(subList); 
return list_of_sublists; 

Sie leicht zu arrays durch die Intervalle immer und Kopieren afterwars jedes Intervall anpassen können.