擅长:python、mysql、java
<p>我想到的一个策略是,我们不必检查距离小于30的两个数字之间的数字,我们可以这样做,因为它是经过排序的。例如,如果<code>abs(hugeArr[0] - hugeArr[-1]) < 30</code>我们不需要检查任何东西,因为没有任何东西的距离会超过30</p>
<p>我们会从末端开始,朝里走。所以首先检查起始号码和结束号码。然后我们走到一半<code>hugeArr[len(hugeArr)//2]</code>,并根据<code>hugeArr[0]</code>和<code>hugeArr[-1]</code>检查数字距离。然后我们进入范围(<code>hugeArr[0:len(hugeArr)//2]</code>和<code>hugeArr[len(hugeArr)//2:-1]</code>)。我们再次将这两个范围一分为二,只要端到端的距离小于30,我们就不检查它们。我们可以把它变成一个递归算法</p>
<p>最坏的情况是,你将有一个超过30的距离,并结束与O(n),但它可以给你一些优势</p>
<p>但是,类似这样的东西可能需要重构为numpy</p>
<pre class="lang-py prettyprint-override"><code>def check(arr):
pairs = []
def check_range(hugeArr):
difference = abs(hugeArr[0] - hugeArr[-1])
if difference < 30:
return
if len(hugeArr) == 2:
pairs.append((hugeArr[0], hugeArr[1]))
return
halfway = len(hugeArr)//2
check_range(hugeArr[:halfway+1])
check_range(hugeArr[halfway:])
check_range(arr)
return pairs
</code></pre>