查找数组是否以子集结束的最简单方法

Question

假设我有一个整数数组:[1, 2, 4, 9, 5, 6, 8, 7]。我有第二个数组，[8, 7, 6]。我想知道的是，第一个数组和第二个数组是否以相同的值结束，不一定以相同的顺序结束?(在本例中，结果应为true)

可依赖的不变量:

• array1.Length > array2.Length
• array1中的所有元素都是唯一的。
• array2中的所有元素都是唯一的。

回答这个问题最简单的方法是什么?如果有一种不需要任何分配的合理有效的解决方案，那就更好了。

Answer 1

你可以有一个简单的0 (nlogn)复杂度(n = size of array2)通过这种方式:

排序array2

• 对array1的最后n个元素排序
• 逐个比较array2和array1的最后n个元素

这应该是您在没有任何额外分配的情况下所能做到的最好的

Answer 2

我认为LINQ是最简单的方法:

using System.Linq;
bool EndsWithSubset(int[] array1, int[] array2)
{
return array1
.TakeLast(array2.Length)
.ToHashSet()
.SetEquals(array2);
}

使用例子:

Console.WriteLine(
EndsWithSubset(
new [] { 1, 2, 4, 9, 5, 6, 8, 7 },
new [] { 8, 7, 6 }
));   // True

Answer 3

您可以在Linq的帮助下查询数组。这里我们利用了所有值都是唯一的(不重复)的事实:

bool contains = !array1
.Skip(array1.Length - array2.Length)
.Except(array2)
.Any();

这里

1. 通过.Skip(array.Length - array2.Length)
获取array1后缀
2. 用.Except(array2)减去array2
3. 检查是否有剩余物品-.Any()

Answer 4

如果第二个数组通常不是很长，您可以对两个序列进行排序并按元素进行比较。如果它很长，排序的成本可能很高，使用哈希集会更有效。

bool endsEqual = arr1.TakeLast(arr2.Length)
.OrderBy(i => i)
.SequenceEqual(arr2.OrderBy(i => i));

Answer 5

使用HashSet来执行此操作:

bool Func(int[] array1, int[] array2)
{
if (array1.Length < array2.Length)
return false;
return new HashSet<int>(array1.Skip(array1.Length - array2.Length)).SetEquals(new HashSet<int>(array2));
}