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

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_itertools
lst = [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):
res = []
lst.sort()
subList = [lst[0]]
for i in range(1, len(lst)):
prev, cur = lst[i-1], lst[i]
if cur - prev > 1:
res.append(subList)
subList = []
subList.append(cur)

res.append(subList)
return res

tests = ([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:
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的运行速度非常快且解决方案很短：
(使用python -m pip install numpy安装numpy后(。

在线试用！

import numpy as np
for l in [
[4,1,5,3],
[4,2,1,3],
[5,2,7,6,3,9],
[1,2,3,4,5,6,8,9,10],
]:
a = np.sort(l)
res = np.split(a, np.flatnonzero(np.abs(np.diff(a)) > 1) + 1)

print('input', l, 'sorted', a, 'n', 'result', res)

输出：

input [4, 1, 5, 3] sorted [1 3 4 5]
result [array([1]), array([3, 4, 5])]
input [4, 2, 1, 3] sorted [1 2 3 4]
result [array([1, 2, 3, 4])]
input [5, 2, 7, 6, 3, 9] sorted [2 3 5 6 7 9]
result [array([2, 3]), array([5, 6, 7]), array([9])]
input [1, 2, 3, 4, 5, 6, 8, 9, 10] sorted [ 1  2  3  4  5  6  8  9 10]
result [array([1, 2, 3, 4, 5, 6]), array([ 8,  9, 10])]