查找列表中的序列

我有我想搜索序列的整數列表。查找列表中的序列

例如，如果我有一個主列表： 1，2，3，4，9,2，39，482，19283，19，23，如圖1所示，29

我想找到序列： 1，2，3，4

我想一些簡單的方法來填充一個子集列表： 1，2，3，4 +未來五年主列表中的整數

，然後取下子集列表中的整數來自主列表，因此在操作結束時，我的列表將如下所示：

主列表： 19，23，如圖1所示，29

子集列表： 1，2，3，4，9,2，39，482，19283

希望是有道理。我猜可能LINQ對於這樣的事情會有好處，但我從來沒有用過。誰能幫忙？

來源

2010-03-11 user113164

提示

，你可以嘗試這樣的事情有一個迭代器一起：

List<int> n = new List<int>() { 1, 2, 3, 4, 9, 2, 39, 482, 19283, 19, 23, 1, 29 }; 
List<int> toFind = new List<int>() { 1, 2, 3, 4 }; 

if (n.Skip(indextostart).Take(4).ToList()==toFind) 
{ 
    n.RemoveRange(indextostart,4); 
}

來源

2010-03-11 21:24:47 Luiscencio

我的直覺告訴我這是O（n * m）而不是O（n），其中n和m分別是要搜索的列表的大小和要查找的列表的大小。 – Brian 2010-03-11 21:28:24

...¿凱和¿... – Luiscencio 2010-03-11 21:30:53

@布萊恩：是的，這是天真的搜索解決方案的最壞情況。還有更多的巧妙算法是O（n + m），但它們涉及對序列進行大量預處理以識別可用於加速搜索的模式。實際上，漸進式算法的「恆定因子」負擔超過了樸素算法的原始速度。在樸素算法中導致性能不佳的病例實際上很少見。 – 2010-03-12 07:01:14

你可以寫一個函數IndexOfSublist可以找到一個列表中的子列表開始。這已經被問過很多次了。

假設你已經實現IndexOfSublist，用它來尋找你的結果的第一個元素，那麼你可以使用GetRange選擇您要保留的元素，然後RemoveRange刪除從原來的列表中的元素。

List<int> l = new List<int> { 1, 1, 2, 3, 4, 9, 2, 39, 482, 19283, 19, 23, 1, 29 }; 
List<int> needle = new List<int> { 1, 2, 3, 4 }; 

int i = indexOfSubList(l, needle); 
if (i != -1) 
{ 
    // TODO: What should we do if there are fewer than four 
    // elements left after the needle? Currently we just throw. 
    List<int> result = l.GetRange(i, needle.Count + 4); 
    l.RemoveRange(i, result.Count); 
    // TODO: Do something with the result; 
}

來源

2010-03-11 21:27:58

查找列表中的序列

回答

相關問題