python - 将连续的整数组合在一起

Question

有如下代码:

import sys


ints = [1,2,3,4,5,6,8,9,10,11,14,34,14,35,16,18,39,10,29,30,14,26,64,27,48,65]
ints.sort()
ints = list(set(ints))

c = {}

for i,v in enumerate(ints):

    if i+1 >= len(ints):
        continue

    if ints[i+1] == v + 1 or ints[i-1] == v - 1:

        if len(c) == 0:
            c[v] = [v]
            c[v].append(ints[i+1])
        else:
            added=False
            for x,e in c.items():
                last = e[-1]
                if v in e:
                    added=True
                    break

                if v - last == 1:
                    c[x].append(v)
                    added=True

            if added==False:
                c[v] = [v]
    else:
        if v not in c:
            c[v] = [v]



print('input ', ints)
print('output ', c))

目标:

给定一个整数列表，创建一个字典，其中包含组合在一起的连续整数以减少列表的总长度。

这是我当前解决方案的输出:

input  [1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 16, 18, 26, 27, 29, 30, 34, 35, 39, 48, 64, 65]
output  {1: [1, 2, 3, 4, 5, 6], 8: [8, 9, 10, 11], 14: [14], 16: [16], 18: [18], 26: [26, 27], 29: [29, 30], 34: [34, 35], 39: [39], 48: [48], 64: [64]}

条件/约束:

• 如果当前整数是 a) 现有列表中的或 b) 现有列表中的最后一项，我们不想为此项创建另一个列表。即在 1-5 范围内，当我们到达 3 时，不要创建列表 3,4，而是将 3 附加到现有列表[1,2]

我当前的迭代工作正常，但由于 for x,e in c.items() 现有列表检查，列表越大，速度越慢。

如何在达到相同结果的同时加快速度？

新解决方案(使用 19,000 个整数的输入列表从 13 秒减少到 0.03 秒):

c = {}

i = 0

last_list = None

while i < len(ints):
    cur = ints[i]

    if last_list is None:
        c[cur] = [cur]
        last_list = c[cur]

    else:

        if last_list[-1] == cur-1:
            last_list.append(cur)
        else:
            c[cur] = [cur]
            last_list = c[cur]

    i += 1

Answer 1

因为你有连续数字的列表，我建议你使用 range 对象而不是 lists:

d, head = {}, None
for x in l:
    if head is None or x != d[head].stop:
        head = x
    d[head] = range(head, x+1)