<p>我试着为这个任务实现3种不同的算法。它们都具有O(N)时间复杂度,需要O(1)个额外的空间。有趣的事实:所有其他答案(目前已知)实现了其中的2个算法(尽管它们并不总是保持最佳的渐近时间/空间复杂度)。下面是每个算法的高级描述:</p>
<p><strong>算法A</strong></p>
<ol>
<li>比较列表,分组“不相等”的间隔,确保正好有两个这样的间隔(特别是当间隔在中间时)。在</li>
<li>检查“非等间距”是否对称放置,其内容是否也“对称”。在</li>
</ol>
<p><strong>算法B</strong></p>
<ol>
<li>比较列表的前半部分,猜测“要交换的间隔”在哪里。在</li>
<li>检查这些间隔的内容是否“对称”。确保这些间隔之外的列表是相等的。在</li>
</ol>
<p><strong>算法C</strong></p>
<ol>
<li>比较列表的前半部分以找到第一个不匹配的元素。在</li>
<li>在第二个列表中找到第一个列表中不匹配的元素。这暗示了“要交换的间隔”的位置。在</li>
<li>检查这些间隔的内容是否“对称”。确保这些间隔之外的列表是相等的。在</li>
</ol>
<p>每种算法的步骤1有两种可选的实现:(1)使用itertools,和(2)使用普通循环(或列表理解)。itertools对于长列表是有效的,但是对于短列表则相对较慢。在</p>
<p>这是算法C,第一步是用itertools实现的。它看起来比其他两种算法更简单(在本文末尾)。而且它的速度非常快,即使对于短名单:</p>
<pre><code>import itertools as it
import operator as op
def test_C(a, b):
length = len(a)
half = length // 2
mismatches = it.imap(op.ne, a, b[:half]) # compare half-lists
try:
n = next(it.compress(it.count(), mismatches))
nr = length - n
mr = a.index(b[n], half, nr)
m = length - mr
except StopIteration: return None
except ValueError: return None
if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
return (n, m)
</code></pre>
<hr/>
<p>这可以主要使用itertools来完成:</p>
^{pr2}$
<p>@j_random_hacker已经在OP评论中提供了该算法的高级描述。以下是一些细节:</p>
<p>从比较列表开始:</p>
^{3}$
<p>然后找出相等/不相等间隔之间的边界:</p>
<pre><code>= E N N E E N N E
B _ * _ * _ * _ *
</code></pre>
<p>然后确定非相等元素的范围:</p>
<pre><code>B _ * _ * _ * _ *
[1 : 3] [5 : 7]
</code></pre>
<p>然后检查是否正好有两个范围(特别是当两个范围在中间相交时),范围本身是对称的,它们的内容也是对称的。在</p>
<hr/>
<p>另一种选择是使用itertools只处理每个列表的一半。这使得算法更简单(也更快),因为不需要处理特殊情况:</p>
<pre><code>def test_B(a, b):
equals = it.imap(op.eq, a, b[:len(a) // 2]) # compare half-lists
e1, e2 = it.tee(equals)
l = it.chain(e1, [True])
r = it.chain([True], e2)
borders = it.imap(op.ne, l, r) # delimit equal/non-equal intervals
ranges = list(it.islice(it.compress(it.count(), borders), 2))
if len(ranges) != 2:
return None
n, m = ranges[0], ranges[1]
nr, mr = len(a) - n, len(a) - m
if a[n:m] == b[mr:nr] and b[n:m] == a[mr:nr] \
and a[m:mr] == b[m:mr] and a[nr:] == b[nr:]:
return (n, m)
</code></pre>