假设有一个这样的数组：
[1,2,3,4,5,6]
另一个像这样(旋转)：
[3,4,5,6,1,2]
有没有简单的方法来判断它们是相等的，或者我应该写一个特定的方法来比较它们？
编辑：当然，第一个数组不应该等于：
[4,3,5,6,1,2] // 4 and 3 are swapped
[1,2,4,3,5,6] // 4 and 3 are swapped
或
[1,2,3,4,5,6,7] // too many items
如果我们有一个数组{a, b, c, .., z}并且我们想找出它是否等于{A, B, ..., Z}我们可以将问题变成等价的
让
abc...z字符串检查ABC...ZABC...Z字符串是否包含abc...z
为了解决这个问题，我们可以使用高效的高德纳-莫里斯-普拉特算法KMP(t ~ O(n))或 如果数组不是很长，请使用易于实现朴素前缀比较(在最坏的情况下t ~ O(n ** 2))：
private static bool MyEquals(int[] left, int[] right)
{
if (ReferenceEquals(left, right))
return true;
if (left is null || right is null)
return false;
if (left.Length != right.Length)
return false;
for (int start = 0; start < right.Length; ++start)
{
bool found = true;
for (int i = 0; i < left.Length; ++i)
if (right[(start + i) % right.Length] != left[i])
{
found = false;
break;
}
if (found)
return true;
}
return false;
}
请注意，
left.OrderBy(x => x).SequenceEqual(right.OrderBy(x => x))
不起作用;反例是{1, 2, 3, 4}vs。{1, 3, 2, 4}上面的代码返回true时应该不相等。
您也可以摆弄我的 KMP 实现。
首先，我们检查第一个列表中的first item of the second列表。如果找到，我们按索引的大小旋转它并比较两个列表：
public bool listCompare(List<int> l1, List<int> l2)
{
int index = l1.FindIndex(a => a == l2[0]);
if(index==-1)
return false;
for(int i=0;i< index;i++)
{
int item = l1[0];
l1.RemoveAt(0);
l1.Add(item);
}
if(l1.SequenceEqual(l2))
return true;
else
return false;
}
如果列表没有重复项，则上述解决方案是正确的。如果存在重复项，则必须检查所有状态。如下：
public bool listCompare2(List<int> l1, List<int> l2)
{
var tempList = l1.Select(item => item).ToList();
var indexs = l1.Select((x, i) => new { x, i })
.Where(x => x.x == l2[0])
.Select(x => x.i).ToArray();
for (int n = 0; n < indexs.Length; n++)
{
int rotateSize = indexs[n];
for (int i = 0; i < rotateSize ; i++)
{
int item = l1[0];
l1.RemoveAt(0);
l1.Add(item);
}
if (l1.SequenceEqual(l2))
return true;
l1 = tempList;
}
return false;
}