Chia danh sách thành các danh sách con dựa trên các giá trị biên giới

Question

Tôi muốn chia nhỏ danh sách được sắp xếp hiện có thành nhiều danh sách con, dựa trên các mục nhập của một danh sách khác.

Hãy nói rằng tôi có một mảng như thế này:

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

và danh sách khác, trong đó xác định tại mà đặt myList nên được chia:

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

con đường ngắn nhất để có được một danh sách lồng nhau là gì trong đó myList được chia theo các giá trị được xác định trong borders, tức là như sau:

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

Tôi đã giải quyết nó bằng cách lặp lại theo cách thủ công thông qua danh sách, nhưng tôi có thể tưởng tượng nó dễ dàng hơn và ngắn hơn khi sử dụng LINQ.

CHỈNH SỬA: Có một cách đơn giản: các số không thể giống với đường viền, vì vậy không thể có một số trong myList và borders cùng một lúc.

Answer 1

Vì bạn muốn nhóm các số thành các nhóm khác nhau, bạn sẽ muốn sử dụng GroupBy. Khó khăn chỉ là những gì bạn sử dụng làm chìa khóa. Đối với điều này, bạn có thể sử dụng giá trị biên lớn nhất nhỏ hơn số. Điều này giả định rằng borders được sắp xếp mặc dù:

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

này mang lại kết quả như sau:

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

Lưu ý rằng đây không phải là chính xác là giải pháp hiệu quả nhất vì nó sẽ tìm kiếm một chốt biên giới phù hợp với mọi phần tử trong myList. Nếu danh sách của bạn được sắp xếp như ví dụ của bạn thì sẽ hiệu quả hơn khi lặp qua cả hai cùng một lúc và chỉ khớp với số của myList đến phần tử biên giới hiện tại hoặc tiếp theo. Vì vậy, giải pháp này là O(n * m) trong khi một giải pháp O(n) là có thể. Về mặt cộng, điều này cho phép myList hoàn toàn không được phân loại.

---

Đối với những người quan tâm đến một O (n) giải pháp, đây là một khả năng đảm nhận nó mà chỉ là một cách rất chung chung về trình tự nhóm:

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