logo标签列表

如何高效地计算一组区间中出现一组数字的次数

pythonlist
6
输入参数是一个表示区间的元组列表和一个整数列表。目标是编写一个函数，计算每个整数在哪些区间中出现，并将结果返回为关联数组。例如：
Input intervals: [(1, 3), (5, 6), (6, 9)]
Input integers: [2, 4, 6, 8]
Output: {2: 1, 4: 0, 6: 2, 8: 1}

另一个例子：

Input intervals: [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)]
Input numbers: [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10]
Output: {2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}

我应该如何编写一个高效的函数来执行此操作？ 我已经实现了O（nm）的算法，其中n是区间的数量，m是整数的数量，但我正在寻找更有效率的解决方案。

我目前所拥有的内容:

def intervals_per_number(numbers, intervals):
    result_map = {i: 0 for i in numbers}
    for i in result_map.keys():
        for k in intervals:
            if k[0] <= i <= k[1]:
                result_map[i] += 1
    return result_map

希望我已经解释得足够清楚了。如果还有什么不明白的，请告诉我。
提前感谢您。
只有列表已排序：调整二分查找。在如此极小的样本上它不会产生太大帮助，但对于长度为8及以上的列表，它应该表现得优秀得多(因为最多只需要3个查找; 对于长度更大，例如百万级别的列表，效果呈指数级增长)。 - Jongware
@usr2564301 你怎么才能比二次方解决方案更快地得到指数级的改进呢？这听起来不太对。 - Kelly Bundy
@HeapOverflow：（哎呀）是的，二次比线性更好。（“指数级”只有2的幂次方倍，不是n。但仍然要好得多。） - Jongware
@usr2564301 嗯，还是不太对。它不是O(n^2)，而是O(n log n)，因此比O(n / log(n))更好？也就是说，它的改进程度小于线性？ - Kelly Bundy
@HeapOverflow 不，区间和整数并不总是已经排序好的。 - STEALTHBOMBER90
3个回答
4
将您的整数、起始点和结束点放入一个成对出现的列表中。将每个成对的第一个元素设置为整数、起始点或结束点的值，将每个成对的第二个元素设置为0、-1或1，取决于它是整数、起始点还是结束点。
接下来，对列表进行排序。
现在，您可以浏览该列表，维护成对元素第二个元素的运行总和。当您看到第二个元素为0的成对时，记录该整数的运行总和（取负）。
在最坏情况下，此操作的时间复杂度为O((N+M)log(N+M))（如果查询和间隔大多已排序，则实际上可能是线性的，感谢timsort）。
例如：
Input intervals: [(1, 3), (5, 6), (6, 9)]
Input integers: [2, 4, 6, 8]

Unified list (sorted):
[(1,-1), (2,0), (3,1), (4,0), (5,-1), (6, -1), (6,0), (6,1), (8,0), (9,1)]

Running sum:
[-1    , -1,    0,     0,      -1,    -2,      0,      -1,    -1,   0]

Values for integers:
2: 1, 4: 0, 6: 2, 8, 1

示例代码：

def query(qs, intervals):
    xs = [(q, 0) for q in qs] + [(x, -1) for x, _ in intervals] + [(x, 1) for _, x in intervals]
    S, r = 0, dict()
    for v, s in sorted(xs):
        if s == 0:
            r[v] = S
        S -= s
    return r

intervals = [(3, 3), (22, 30), (17, 29), (7, 12), (12, 34), (18, 38), (30, 40), (5, 27), (19, 26), (27, 27), (1, 31), (17, 17), (22, 25), (6, 14), (5, 7), (9, 19), (24, 28), (19, 40), (9, 36), (2, 32)]
queries = [16, 18, 39, 40, 27, 28, 4, 23, 15, 24, 2, 6, 32, 17, 21, 29, 31, 7, 20, 10]
print(query(queries, intervals))

输出：

{2: 2, 4: 2, 6: 5, 7: 6, 10: 7, 15: 6, 16: 6, 17: 8, 18: 8, 20: 9, 21: 9, 23: 11, 24: 12, 27: 11, 28: 9, 29: 8, 31: 7, 32: 6, 39: 2, 40: 2}
0

你可以预先对 整数 进行排序，然后在下限上使用 bisect_left。排序的复杂度为 O(M*log(M))，而 bisect 的复杂度为 O(log(M))。因此，实际上你有 O(max(M, N) * log(M))。

import bisect
from collections import defaultdict

result = defaultdict(int)
integers = sorted(integers)
for low, high in intervals:
    index = bisect.bisect_left(integers, low)
    while index < len(integers) and integers[index] <= high:
        result[integers[index]] += 1
        index += 1
1
看起来你的复杂度分析忘记了 while 循环。 - Kelly Bundy
1
@HeapOverflow 的确如此，但这取决于间隔的分布情况。如果它们大多数不重叠（或者重叠的数量是恒定的），那么这会增加常数时间。 - a_guest
0

根据使用情况和上下文，简单的东西可能就足够了：

from collections import Counter
from itertools import chain

counts = Counter(chain.from_iterable(range(f, t+1) for f,t in input_intervals))
result = {k:counts[k] for k in input_numbers}

O(n*k + m) 其中 n 是区间数量，k 是平均区间大小，m 是整数数量。

网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接