有以下代码:
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