这里已经有很多好的答案,包括被接受答案的很好的解释。然而,我想指出Python语言实现细节方面的一个小观察。
最初,我提出了下面所示的解决方案。我期望得到O(N*log(N))
的时间复杂度,因为我们有一个单独的for循环,其中每个迭代执行最多需要log(N)
的二分查找。
def solution(a):
import bisect
if len(a) <= 1:
return 0
cuts = [(c - r, c + r) for c, r in enumerate(a)]
cuts.sort(key=lambda pair: pair[0])
lefts, rights = zip(*cuts)
n = len(cuts)
total = 0
for i in range(n):
r = rights[i]
pos = bisect.bisect_right(lefts[i+1:], r)
total += pos
if total > 10e6:
return -1
return total
然而,我得到了 O(N**2)
和超时失败。你看到问题在哪里了吗?没错,就是这行代码:
pos = bisect.bisect_right(lefts[i+1:], r)
在这行代码中,你实际上是
复制 原始列表并将其传递到二分查找函数中,这完全破坏了所提出解决方案的效率!它使您的代码更加简洁(即,您不需要编写
pos - i - 1
),但严重削弱了性能。因此,如上所示,解决方案应为:
def solution(a):
import bisect
if len(a) <= 1:
return 0
cuts = [(c - r, c + r) for c, r in enumerate(a)]
cuts.sort(key=lambda pair: pair[0])
lefts, rights = zip(*cuts)
n = len(cuts)
total = 0
for i in range(n):
r = rights[i]
pos = bisect.bisect_right(lefts, r)
total += (pos - i - 1)
if total > 10e6:
return -1
return total
似乎有时候人们过于热衷于进行切片和复制,因为Python让这些操作变得非常容易 :) 对我来说,这可能不是一个很好的见解,但这是一个很好的教训,提醒我在将想法和算法转化为现实解决方案时要更加注意这些“技术”细节。