拆分整数列表，使它们产生具有最小差异的子列表

Question

我将如何拆分整数列表，以便将它们放在子列表中且差异最小？

例如

[4,1,5,3] --> [[1], [3,4,5]]，长度 2

[4,2,1,3] --> [[1,2,3,4]]，长度 1

[5,2,7,6,3,9] --> [[2,3], [5,6], [9]]，长度 3

[1,2,3,4,5,6,8,9,10] --> [[1,2,3,4,5,6], [8,9,10]]，长度 2。

目前的方法是

def split(l): 

    res = [] 

    n = len(l) 

    l.sort() 

    # If the list is just consecutive integers return 1

    if l == list(range(min(l), max(l)+1)): 

        return 1  

    for l0, l1 in zip(l, l[1:]): 

        if abs(l0 - l1) <= 1: 

           res.append([l0, l1]) 

    return len(res)

这适用于前三种情况，但最后一种失败了...我认为问题是在循环中我只是通过两个连续整数的差异进行调节...

Answer 1

如果您被允许使用外部包，则more_itertools具有split_when方法，它可以满足您的需求：import more_itertoolslst = [1,2,3,4,5,6,8,9,10]lst.sort()splitted = list(more_itertools.split_when(lst, lambda x, y: abs(x-y) > 1))print(splitted)输出：[[1, 2, 3, 4, 5, 6], [8, 9, 10]]

Answer 2

我只是检查两个数字之间的差是否大于 1：def mySplit(lst):&nbsp; &nbsp; res = []&nbsp; &nbsp; lst.sort()&nbsp; &nbsp; subList = [lst[0]]&nbsp; &nbsp; for i in range(1, len(lst)):&nbsp; &nbsp; &nbsp; &nbsp; prev, cur = lst[i-1], lst[i]&nbsp; &nbsp; &nbsp; &nbsp; if cur - prev > 1:&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; res.append(subList)&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; subList = []&nbsp; &nbsp; &nbsp; &nbsp; subList.append(cur)&nbsp;&nbsp; &nbsp; res.append(subList)&nbsp; &nbsp; return restests = ([4,1,5,3], [4,2,1,3], [5,2,7,6,3,9], [1,2,3,4,5,6,8,9,10,13])for test in tests:&nbsp; &nbsp; print(mySplit(test))出去：[[1], [3, 4, 5]][[1, 2, 3, 4]][[2, 3], [5, 6, 7], [9]][[1, 2, 3, 4, 5, 6], [8, 9, 10], [13]]

Answer 3

numpy使用：运行速度非常快且简短的解决方案（一旦使用安装numpy&nbsp;python -m pip install numpy）。在线尝试一下！import numpy as npfor l in [&nbsp; &nbsp; [4,1,5,3],&nbsp; &nbsp; [4,2,1,3],&nbsp; &nbsp; [5,2,7,6,3,9],&nbsp; &nbsp; [1,2,3,4,5,6,8,9,10],]:&nbsp; &nbsp; a = np.sort(l)&nbsp; &nbsp; res = np.split(a, np.flatnonzero(np.abs(np.diff(a)) > 1) + 1)&nbsp; &nbsp;&nbsp;&nbsp; &nbsp; print('input', l, 'sorted', a, '\n', 'result', res)输出：input [4, 1, 5, 3] sorted [1 3 4 5]&nbsp;result [array([1]), array([3, 4, 5])]input [4, 2, 1, 3] sorted [1 2 3 4]&nbsp;result [array([1, 2, 3, 4])]input [5, 2, 7, 6, 3, 9] sorted [2 3 5 6 7 9]&nbsp;result [array([2, 3]), array([5, 6, 7]), array([9])]input [1, 2, 3, 4, 5, 6, 8, 9, 10] sorted [ 1&nbsp; 2&nbsp; 3&nbsp; 4&nbsp; 5&nbsp; 6&nbsp; 8&nbsp; 9 10]&nbsp;result [array([1, 2, 3, 4, 5, 6]), array([ 8,&nbsp; 9, 10])]