对 Python 中的一组值进行分区

Question

我编写了一个函数，试图将值列表划分为连续的块。块是一组值，其中从开始到结束的值将出现在列表中。例如，考虑列表 [1,2,3,7,7,8,9]。这将被划分为 {1:3, 7:3}。稍后我可以将其读作 interval that starts at 1 of length 3 and an interval that starts at 7 of length 3.

我想出了以下代码：-

values = list(set(values))
values.sort()
ranges = {}
for value in values:
    if value - i in ranges:
        ranges[value-i] += 1
        i += 1
    else:
        i = 1
        ranges[value] = 0

我很好奇这是否是最好的方法。将列表转换为集合并返回列表的时间复杂度是多少？我猜那将是 O(n)。

对于如何做得更好，您有什么建议吗？

Answer 1

我们可以做线性的：

values = [7, 3, 2, 7, 1, 9, 8]

range_by_min, range_by_max = {}, {}

for v in values:
    range_by_min[v] = range_by_max[v] = [v, v]

for v in values:
    if v - 1 in range_by_max and v in range_by_min:
        p, q = range_by_max[v - 1], range_by_min[v]
        del range_by_min[q[0]]
        del range_by_max[p[1]]
        p[1] = q[1]
        range_by_max[p[1]] = p

print(range_by_min, range_by_max)

result = {k: v[1] - v[0] + 1 for k, v in range_by_min.iteritems()}
print(result)

结果：

({1: [1, 3], 7: [7, 9]}, {3: [1, 3], 9: [7, 9]})
{1: 3, 7: 3}

想法是保留两个存储范围的字典（范围表示为它的最小值和最大值的列表）。第一个将最小键映射到范围。第二个将最大键映射到范围。

然后我们遍历值列表并加入相邻范围。如果我们正在访问 4 并且有一个范围 4..6 那么我们检查是否有一个范围以 3 结尾，比方说 1..3。所以我们将它们合二为一：1..6.

该算法与哈希 table 访问呈线性关系。由于我们期望不断访问字典，因此预期的运行时间与值的大小成线性关系。通过这种方式，我们甚至不必对输入数组进行排序。

编辑:

我看到了 David Eisenstat 建议的 link。基于这个link，实现可以更新为只使用一个字典：

ranges = {v: [v, v] for v in values}

for v in values:
    if v - 1 in ranges and v in ranges:
        p, q = ranges[v - 1], ranges[v]
        if p[1] == v - 1 and q[0] == v:
            if q[0] != q[1]:
                del ranges[q[0]]
            if p[0] != p[1]:
                del ranges[p[1]]
            p[1] = q[1]
            ranges[p[1]] = p

result = {k: v[1] - v[0] + 1 for k, v in ranges.iteritems() if k == v[0]}

对 Python 中的一组值进行分区

Partitioning a set of values in Python

python

algorithm

big-o

dictionary

data-structures