如何解决这个问题（leetcode 风格的技术问题）？

Question

假设给你一个整数对列表

pairs

和两个整数

k1

和

k2

.
从满足以下条件的列表中找出对的数量：

• pairs[i][0] + pairs[j][0] <= k1

• pairs[i][1] + pairs[j][1] <= k2

• 对于

  i < j

例如，如果，

pairs=[[1,2],[2,3],[3,4],[4,5]]

，

k1=6

和

k2=7

，结果应该是

4

，因为

([1,2],[2,3])

，

([1,2],[3,4])

，

([1,2],[4,5])

和

([2,3],[3,4])

都满足上述条件

有关问题的更好描述，请参见图片：

有没有比O(n^2)效率更高的方法来解决这个问题？到目前为止，这是我的解决方案：

pairs = [[1,2],[2,3],[3,4],[4,5]]
k1 = 6
k2 = 7

count = 0
n = len(pairs)

for i in range(n):
    for j in range(i+1, n):
        if pairs[i][0]+pairs[j][0] <= k1 and pairs[i][1]+pairs[j][1] <= k2:
            count += 1

print(count)

Answer 1

这是 O(n log n) 并在大约 1.5 秒内解决了最大允许输入 (n=2×10^5)：

pairs = deque(sorted(pairs))
ys = SortedList(y for _, y in pairs)
count = 0
while pairs:
    x, y = pairs[0]
    X, Y = pairs[-1]
    if x + X <= k1:
        ys.remove(y)
        count += ys.bisect_right(k2 - y)
        pairs.popleft()
    else:
        ys.remove(Y)
        pairs.pop()

将这些对视为 (x,y) 对。按 x 坐标对它们进行排序，然后向内移动。设 (x,y) 为最左边的一对，(X,Y) 为最右边的一对。

• 如果 x+X ≤ k1，那么，关于 x 坐标，最左边的一对可以与 all 其他对组合（因为 X 是 最大的）。但其中有多少也有合适的 y 坐标，即 y+y_other ≤ k2？这意味着 y_other ≤ k2-y。为此，我们将所有 y 坐标保存在一个排序列表中。因为我们想要 other 对，我们首先删除最左边的对自己的 y。然后我们对 k2-y 进行二进制搜索，它告诉我们适合其他对的数量。最后，我们从进一步考虑中删除了最左边的一对，因为我们计算了它的所有贡献。

• 如果 x+X > k1，则最右边的一对 X 太大，无法与任何其他对组合。所以我们只需从 y 列表中删除它的 Y 并删除该对。

我在那里用过

SortedList

。如果我们改用 Python

list

，则该算法需要 O(n^2)，因为

del

需要线性时间。但是有一个非常小的常数因子，所以它仍然只需要大约 3 秒的最大允许输入。

用你的小例子和更大的随机输入测试结果：

4 pairs:
  count=4  0.000 s  original
  count=4  0.000 s  Kelly_SortedList
  count=4  0.000 s  Kelly_list

1000 pairs:
  count=51328  0.144 s  original
  count=51328  0.003 s  Kelly_SortedList
  count=51328  0.002 s  Kelly_list

6000 pairs:
  count=1845645  4.786 s  original
  count=1845645  0.023 s  Kelly_SortedList
  count=1845645  0.012 s  Kelly_list

200000 pairs:
  count=2022417695  1.490 s  Kelly_SortedList
  count=2022417695  2.944 s  Kelly_list

400000 pairs:
  count=8075422313  3.454 s  Kelly_SortedList
  count=8075422313 12.957 s  Kelly_list

代码：

from bisect import bisect_left, bisect_right
from collections import deque
from random import randrange
from time import perf_counter as time
from sortedcontainers import SortedList


def original(pairs, k1, k2):
    count = 0
    n = len(pairs)
    for i in range(n):
        for j in range(i+1, n):
            if pairs[i][0]+pairs[j][0] <= k1 and pairs[i][1]+pairs[j][1] <= k2:
                count += 1
    return count


def Kelly_SortedList(pairs, k1, k2):
    pairs = deque(sorted(pairs))
    ys = SortedList(y for _, y in pairs)
    count = 0
    while pairs:
        x, y = pairs[0]
        X, Y = pairs[-1]
        if x + X <= k1:
            ys.remove(y)
            count += ys.bisect_right(k2 - y)
            pairs.popleft()
        else:
            ys.remove(Y)
            pairs.pop()
    return count


def Kelly_list(pairs, k1, k2):
    pairs = deque(sorted(pairs))
    ys = sorted(y for _, y in pairs)
    count = 0
    while pairs:
        x, y = pairs[0]
        X, Y = pairs[-1]
        if x + X <= k1:
            del ys[bisect_left(ys, y)]
            count += bisect_right(ys, k2 - y)
            pairs.popleft()
        else:
            del ys[bisect_left(ys, Y)]
            pairs.pop()
    return count


funcs = original, Kelly_SortedList, Kelly_list

def test(funcs, *args):
    print(len(args[0]), 'pairs:')
    for f in funcs:
        t0 = time()
        print(f'  count={f(*args)}', f'{time() - t0 :6.3f} s ', f.__name__)
    print()

def gen(n):
    pairs = [[randrange(2*10**5), randrange(2*10**5)] for _ in range(n)]
    k1 = 15 * 10**4
    k2 = 17 * 10**4
    return pairs, k1, k2

test(funcs, [[1,2],[2,3],[3,4],[4,5]], 6, 7)
test(funcs, *gen(1000))
test(funcs, *gen(6000))
test(funcs[1:], *gen(2*10**5))
test(funcs[1:], *gen(4*10**5))

Answer 2

这里是

O(n)

空间和

O(n log n)

时间。给定一个顺序统计树，

ys

，这些对按其第一个元素排序；和两个指针，

r

在最后一对的索引处，

l

在 0:

result = 0
while r > l:
  while pairs[l][0] + pairs[r][0] <= k1:
    add pairs[l][1] to ys
    l += 1
  result += count of ys <= (k2 - pairs[r][1])
  r -= 1
return result

这会在正确的索引处添加每对可以匹配的对数。随着窗口变窄，左侧的所有对（具有较小的第一个元素）仍然是候选对象，并且可以添加更多对，因为右侧的固定对具有越来越小的第一个元素。顺序统计树帮助我们回答右边的对有多少左边的候选人也遵守第二个元素限制。