将连续的整数组合在一起 [英] Group consecutive integers together

问题描述

具有以下代码:

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))

目标:

给出一个整数列表，创建一个字典，其中包含连续的整数，这些整数被分组在一起以减少列表的总长度.

Given a list of integers, create a dictionary that contains consecutive integers grouped together to reduce the overall length of the list.

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

Here is output from my current solution:

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或b)是现有列表中的最后一个项目，则我们不想为此项目创建另一个列表.也就是说，在1-5范围内(包括1-5)，当我们到达 3 时，不要创建列表 3,4 ，而是将 3 附加到现有列表 [1,2]

• If the current integer is either a) in an existing list or b) is the last item in an existing list, we don't want to create another list for this item. i.e. in the range 1-5 inclusive, when we get to 3, don't create a list 3,4, instead append 3 to the existing list [1,2]

我当前的迭代效果很好，但是列表越大，它的速度就成倍地降低，这是因为c.items()中现有列表检查中x，e的.

My current iteration works fine, but it gets exponentially slower the bigger the list is because of the for x,e in c.items() existing list check.

如何在保持相同结果的同时加快速度?

How can I make this faster while still achieving the same result?

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

New solution (from 13 seconds to 0.03 seconds using an input list of 19,000 integers):

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

推荐答案

由于您有连续数字列表，因此建议您使用 range 对象而不是 list s:

As you have lists of consecutive numbers, I suggest you to use range objects instead of 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)

这篇关于将连续的整数组合在一起的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！