假設有一個這樣的陣列：
[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
uj5u.com熱心網友回復：
如果我們有一個陣列{a, b, c, .., z}并且我們想找到它是否等于，{A, B, ..., Z}我們可以將問題轉化為等價
有
abc...z字串檢查ABC...ZABC...Z字串是否包含abc...z
為了解決這個問題，我們可以使用高效的 Knuth-Morris-Pratt 演算法 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 實作。
uj5u.com熱心網友回復：
首先，我們檢查第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;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/net/520446.html
標籤：C＃。网算法
上一篇：如何降低此演算法的時間復雜度？