Geteilte Liste in Unterlisten basierend auf Grenzwerten

Question

Ich möchte eine bestehende sortierte Liste in mehrere Unterlisten basierend auf den Einträgen einer anderen Liste aufteilen.

Sagen wir, ich habe ein Array wie folgt aus:

List<int> myList = [1,3,7,23,56,58,164,185]; 

und eine weitere Liste, die in dem definiert orte myList aufgeteilt werden sollte:

List<int> borders = [4,59,170]; 

Was ist der kürzeste Weg, um eine verschachtelte Liste zu erhalten Dabei wird myList auf die in borders definierten Werte aufgeteilt, dh wie folgt:

[[1,3],[7,23,56,58],[164],[185]] 

Ich habe es schon gelöst, indem ich manuell die Listen durchgeblättert habe, aber ich kann mir vorstellen, dass es mit Linq einfacher und kürzer ist.

EDIT: Es gibt eine Vereinfachung: Zahlen können nicht die gleichen wie die Grenzen sein, so ist es unmöglich, dass eine myList und borders zur gleichen Zeit enthalten ist.

Answer 1

Da Sie die Nummern in verschiedenen Gruppen gruppieren möchten, sollten Sie GroupBy verwenden. Die Schwierigkeit besteht nur darin, was Sie als Schlüssel verwenden. Dazu können Sie den größten Grenzwert verwenden, der kleiner als die Zahl ist. Dies setzt voraus, dass borders obwohl sortiert:

List<int> myList = new List<int> { 1, 3, 7, 23, 56, 58, 164, 185 }; 
List<int> borders = new List<int> { 4, 59, 170 }; 

var groups = myList.GroupBy(i => borders.LastOrDefault(x => x < i)); 

foreach (var group in groups) 
{ 
    Console.WriteLine("{0}: {1}", group.Key, string.Join(", ", group)); 
} 

Dies ergibt die folgende Ausgabe:

0: 1, 3 
4: 7, 23, 56, 58 
59: 164 
170: 185 

Beachten Sie, dass dies nicht genau die effizienteste Lösung, da es für jedes Element für eine angemessene Grenze Schlüssel suchen in myList. Wenn Ihre Liste wie in Ihrem Beispiel sortiert ist, ist es effizienter, beide gleichzeitig zu durchlaufen und nur die Zahlen von myList mit dem aktuellen oder nächsten Rahmenelement abzugleichen. So ist diese Lösung O(n * m) während eine Lösung O(n) möglich ist. Auf der positiven Seite erlaubt dies myList vollständig unsortiert zu sein.

---

Für Interessenten an einem O (n) Lösung, hier ist man auf es möglich, nimmt die auf Gruppierung Sequenzen nur eine sehr allgemeine Art und Weise ist:

List<List<int>> groups = new List<List<int>>(); 
List<int> group = null; 
int k = -1; 
foreach (int num in myList) 
{ 
    if (k < 0 || num > borders[k]) 
    { 
     group = new List<int>(); 
     groups.Add(group); 
     k++; 
    } 
    group.Add(num); 
}