<p>我不知道你为什么在这里排队。它似乎不是解决这个问题的正确数据结构。此外,Python有一个内置的队列数据结构(<code>collections.deque</code>,只使用<code>popleft()</code>而不是<code>pop(0)</code>)。你知道吗</p>
<p>一种更简单的方法(imo)是只维护指向每个数组的“指针”(或索引),从开始处开始。如果元素彼此在<code>approx</code>范围内,则添加它们,并递增两个指针。如果<code>a</code>的元素小于<code>b</code>的元素,则增加<code>a</code>的指针。否则,增加<code>b</code>的指针。继续,直到两个指针都用完(即指向列表的末尾)。它以O(N),线性时间运行。下面是上述算法的实现:</p>
<pre><code>def match_approximate(a, b, approx=3):
a_ind, b_ind = 0, 0
result = []
while a_ind < len(a) and b_ind < len(b):
if abs(a[a_ind] - b[b_ind]) <= approx:
result.append(b[b_ind])
if a[a_ind] == b[b_ind]:
b_ind += 1
a_ind += 1
elif a[a_ind] < b[b_ind]: a_ind += 1
else: b_ind += 1
def match_last_element(a, a_ind, last_elt_of_b, result):
while a_ind != len(a):
if abs(a[a_ind] - last_elt_of_b) <= approx:
result.append(a[a_ind])
a_ind += 1
else:
break
if a_ind != len(a): match_last_element(a, a_ind, b[-1], result)
else: match_last_element(b, b_ind, a[-1], result)
return result
</code></pre>
<p>跑步</p>
<pre><code>a = [7, 22, 34, 49, 56, 62, 76, 82, 89, 161, 163, 174]
b = [5, 6, 7, 14, 49, 57, 66, 76, 135, 142, 161]
print(match_approximate(a, b, 3))
</code></pre>
<p>将输出<code>[5, 6, 7, 49, 57, 76, 161, 163]</code>(这是我<em>假设</em>所期望的,但是请参见下面关于一些不清楚的边缘情况的内容)。如果您在当前impl上运行这个案例,您将得到一个<code>IndexError</code>。你知道吗</p>
<p>在某些边缘情况下,我们还不完全清楚该怎么办:</p>
<ol>
<li><p>当你有一个近似匹配时,你会在结果中添加哪个元素?这个impl只是拉入<code>b</code>的元素(如示例所示)。</p></li>
<li><p>应如何处理重复项?在这个impl中,如果两个列表都包含一个dup,它将被添加两次。如果只有一个列表包含重复项,则只添加一次元素。关于dup的一个更复杂的例子是理解如果我们有<code>[4,5]</code>和<code>[4,5]</code>作为输入,那么我们的输出应该是<code>[4,5]</code>还是<code>[4,4,5,5]</code>(因为<code>4</code>和<code>5</code>都在<code>approx</code>之内,<code>4</code>也与<code>5</code>匹配)。</p></li>
<li><p>绑定的<code>approx</code>是包含的还是独占的(即<code><= approx</code>或<code>< approx</code>)?</p></li>
</ol>
<p>请随意调整上述impl,以处理您认为在这些情况下需要执行的任何操作。你知道吗</p>
<p>嗯。你知道吗</p>