将数字列表拆分为具有连续数字的子列表

Question

我想将数字列表中的数字分组到子列表中。子列表中必须是连续的数字

输入==>

[-4,-3,-2,0,1,3,5,6,7,17,18,30]

输出 ==>

[[-4,-3,-2],[0,1],[3],[5,6,7],[17,18],[30]]

最好没有库（只有泛型）

Answer 1

发电机可以很好地完成这类事情。

代码

def group_me(list):
    list.sort()
    sublist = []

    while list:
        v = list.pop(0)

        if not sublist or sublist[-1] in [v, v-1]:
            sublist.append(v)
        else:
            yield sublist
            sublist = [v]

    if sublist:
        yield sublist


list = [-4, -3, -2, 0, 1, 3, 5, 6, 7, 17, 18, 30]
result = [sublist for sublist in group_me(list)]
print(result)

输出

[[-4, -3, -2], [0, 1], [3], [5, 6, 7], [17, 18], [30]]

注释

如果输入列表中有重复项，则会将它们放入同一个子列表中。

Answer 2

为此，您可以简单地使用 for 循环。一次通过是我们能做的最好的事情——我们必须对每个元素检查一次。这是 big-O 表示法中的 O(n)。

记住列表必须是排序的，否则不起作用。

代码：

inpt = [-4,-3,-2,0,1,3,5,6,7,17,18,30]

rv = []

# Set up current list with first element of input
curr = [inpt[0]]

# For each remaining element:
for x in inpt[1:]:
    # If the next element is not 1 greater than the last seen element
    if x - 1 != curr[-1]:
        # Append the list to the return variable and start a new list
        rv.append(curr)
        curr = [x]
    # Otherwise, append the element to the current list.
    else:
        curr.append(x)
rv.append(curr)

输出：

>>> rv
[[-4, -3, -2], [0, 1], [3], [5, 6, 7], [17, 18], [30]]

Answer 3

双指针解决方案

a = [-4,-3,-2,0,1,3,5,6,7,17,18,30]
slow, fast = 0,0
ans, temp = [], []
while fast < len(a):
    if fast - slow == a[fast] - a[slow]:
        temp.append(a[fast])
        fast += 1
    else:
        slow = fast
        ans.append(temp)
        temp = []
if fast > slow:
    ans.append(temp)
print(ans)

Answer 4

您可以使用二分查找来查找数字列表中最后一个连续值的最大索引。二分搜索是查找元素位置的有效方法，我们可以使用它通过将值与其各自的索引进行比较来识别连续子列表的末尾。

# Binary search to find the end of the continuous sequence
def find_max_continuous_index(arr):
    n = len(arr)
    left, right = 0, n - 1
    while left < right:
        mid = (left + right + 1) // 2
        if arr[mid] == arr[0] + mid:
            left = mid
        else:
            right = mid - 1

    return left

continuous_sublists = []
start = 0

while start < len(input):
    end = find_max_continuous_index(input[start:]) + start
    continuous_sublists.append(input[start:end + 1])
    start = end + 1