如何检查列表是否包含按相同顺序排列的另一个列表
本文关键字:列表 顺序 排列 另一个 包含按 是否 何检查 检查 | 更新日期: 2023-09-27 18:28:57
c#中有没有简单的方法来检查列表是否由另一个列表组成?。这里是一个例子,我有:
var list1 = new List<int>() {1, 2, 3, 4, 5, 6,};
第二个var list2 = new List<int>() {5, 6};
这个列表是第一个列表的一部分,所以它应该返回true。
var list1 = new List<int>() {1, 2, 3, 4, 5, 6,};
和var list3 = new List<int>() {1, 3};
应返回false。
这不是关于检查第一个列表中的所有元素是否都存在于第二个列表中,而是关于顺序。它必须有相同的顺序。
这对我有效:
public bool ContainsSubsequence<T>(List<T> sequence, List<T> subsequence)
{
return
Enumerable
.Range(0, sequence.Count - subsequence.Count + 1)
.Any(n => sequence.Skip(n).Take(subsequence.Count).SequenceEqual(subsequence));
}
此代码使用Enumerable.Range
来遍历sequence
中可能与subsequence
相同的每个可能的起点,并检查与subsequence
大小相同的sequence
在该位置的分段是否实际等于subsequence
。
所以对于这个代码:
var list1 = new List<int>() { 1, 2, 3, 4, 5, 6, };
var list2 = new List<int>() { 5, 6, };
var list3 = new List<int>() { 1, 3, };
Console.WriteLine(ContainsSubsequence(list1, list2));
Console.WriteLine(ContainsSubsequence(list1, list3));
我得到:
True
False
感谢@GeorgeVovos&指出第一个解决方案中的问题的怀疑态度。
public static bool HasSubSequence(List<int> main, List<int> query)
{
var startIndex = main.IndexOf(query.First());
if (main == null || query == null || startIndex < 0)
return false;
while (startIndex >= 0)
{
if (main.Count - startIndex < query.Count)
return false;
var nonMatch = false;
for (int i = 0; i < query.Count; i++)
{
if (main[i + startIndex] != query[i])
{
main = main.Skip(startIndex + 1).ToList();
startIndex = main.IndexOf(query.First());
nonMatch = true;
break;
}
}
if (!nonMatch)
return true;
}
return false;
}
示例
var l1 = new List<int> { 1, 2, 3, 4, 5 };
var l2 = new List<int> { 4, 5 };
var l3 = new List<int> { 1, 3 };
var l4 = new List<int> { 5, 6 };
var l5 = new List<int> { 1, 2, 3, 2, 5, 6, 2, 4, 8 };
var l6 = new List<int> { 2, 4 };
var test1 = HasSubSequence(l1, l2); //true
var test2 = HasSubSequence(l1, l3); //false
var test3 = HasSubSequence(l1, l4); //false
var test5 = HasSubSequence(l5, l6); //true