如何在列表中找到子列表的索引?
我正在寻找一些有效的方法(在.NET中),如何查找某些字节列表中是否存在字节序列以及是否存在第一个启动的索引。
例如,假设我有:
var sequence = new List { 5, 10, 2 }; var listOne = new List { 1, 3, 10, 5, 10, 2, 8, 9 }; var listTwo = new List { 1, 3, 10, 5, 2, 10, 8, 9 };
结果应该是我的序列在listOne中的索引3和listTwo中的索引-1(即它不存在)上。
当然,我可以通过int和每个索引循环遍历列表int并搜索以下数字是否与我的序列匹配,但是是否有一些更有效的方法(例如使用扩展方法)?
这与子字符串搜索基本上是相同的问题(实际上,顺序有效的列表是“字符串”的概括)。
幸运的是,计算机科学长期以来经常考虑这个问题,所以你要站在巨人的肩膀上。
看看文献。 一些合理的起点是:
https://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm
https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string_search_algorithm
https://en.wikipedia.org/wiki/Rabin-karp
即使只是维基百科文章中的伪代码也足以轻松移植到C#。 查看不同情况下的性能描述,并确定代码最可能遇到的情况。 (我正在考虑你所说的搜索键列表中的第一个是简短的)。
我认为最干净的方法是创建一个通用的扩展方法,如下所示:
public static int SubListIndex(this IList list, int start, IList sublist) { for (int listIndex = start; listIndex < list.Count - sublist.Count + 1; listIndex++) { int count = 0; while (count < sublist.Count && sublist[count].Equals(list[listIndex + count])) count++; if (count == sublist.Count) return listIndex; } return -1; }
以这种方式打电话:
var indexOne = listOne.SubListIndex(0, sequence); var indexTwo = listTwo.SubListIndex(0, sequence);
如果您需要搜索更多的子列表出现,PS也可以从给定的索引开始
我建议将每个List
转换为String
,然后使用String.IndexOf(sequence)
进行搜索,以确定String.IndexOf(sequence)
在何处或是否存在。
上述就是C#学习教程:如何在列表中找到子列表的索引?分享的全部内容,如果对大家有所用处且需要了解更多关于C#学习教程,希望大家多多关注—计算机技术网(www.ctvol.com)!
本文来自网络收集,不代表计算机技术网立场,如涉及侵权请联系管理员删除。
ctvol管理联系方式QQ:251552304
本文章地址:https://www.ctvol.com/cdevelopment/998372.html