Ayraç Listesini sınır değerlere göre ayırma listesi

Question

Başka bir listenin girişlerine dayalı olarak, mevcut bir sıralanmış listeyi birden fazla alt listeye ayırmak istiyorum.

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

yuvalanmış bir listesini almak için en kısa yolu nedir: hangi myList bölünmüş olmalıdır yerleştiren tanımlar

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

ve başka bir liste,:

en Böyle bir dizi var diyelim Burada myList, borders'da tanımlanan değerlere bölünmüştür, örneğin:

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

Listeden el ile geçerek bunu zaten çözdüm, ancak Linq kullanarak daha kolay ve daha kısa olduğunu hayal edebiliyorum.

DÜZENLEME: Bir basitleştirme var: Sayılar kenarlıklarla aynı olamaz, bu nedenle myList ve borders'da aynı anda bir sayının bulunması imkansızdır.

Answer 1

Sayıları farklı gruplara ayırmak istediğinizden, GroupBy'u kullanmak isteyeceksiniz. Zorluk sadece anahtar olarak kullandığınız şeydir. Bunun için, sayıdan daha küçük olan en büyük sınır değerini kullanabilirsiniz. Bu da her eleman için uygun bir sınır anahtarının arar gibi en verimli çözüm tam olmadığını

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

Not:

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)); 
} 

Bu aşağıdaki çıktı verir: Bu borders olsa sıralanır varsayar myList. Listeniz örneğiniz gibi sıralanırsa, aynı anda hem döngüsel olarak hem de geçerli veya sonraki kenarlık öğesine myList numaralarını eşleştirmek daha verimlidir. Bu yüzden bu çözüm O(n)O(n) mümkün iken O(n * m). Artı tarafta, bu, myList'un tamamen kaldırılmasına izin verir.

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); 
}