谁能提供一个方法吗?
将列表划分为子列表,使子列表中任意两个元素之间的绝对差值不超过'k'值。无论顺序如何,都可以形成子列表。子列表可以包含任意数量的元素。子列表的数量应该是最少的
Example:
arr=[1,5,4,6,8,9,2]
k=3
sublists generated are [[2,1],[5,4,6],[8,9]]
Example 2:
arr=[1,13,6,8,9,3,5]
k=4
sublists generated are [[1,3,5],[6,8],[13,9]]
我们需要返回子列表的最小数目,其中两个列表之间的差不能超过k。一个元素只能在一个子列表中
# easier version
arr = sorted(arr)
lst = []
sublist = [arr.pop(0)]
while len(arr) > 0:
item = arr.pop(0)
if item - sublist[0] >= k:
lst.append(sublist)
sublist = [item]
else:
sublist.append(item)
lst.append(sublist)
print(lst)
# shorter version
arr = sorted(arr)
lst = [[arr.pop(0)]]
while len(arr) > 0:
item = arr.pop(0)
lst.append([item]) if item - lst[-1][0] >= k else lst[-1].append(item)
print(lst)
def ex(arr, k):
arr = sorted(arr)
new_lst = []
sub_lst = [arr[0]]
for i in range(1, len(arr)):
if arr[i] - sub_lst[0] < k:
sub_lst.append(arr[i])
else:
new_lst.append(sub_lst)
sub_lst = [arr[i]]
new_lst.append(sub_lst)
return new_lst
arr = [1, 13, 6, 8, 9, 3, 5]
k = 4
print(ex(arr, k))
小解释:我们正在整理列表。然后我们检查第一个元素的匹配项。因为列表是有序的,所以它们在列表中就在他旁边。如果下一个元素不匹配,我们可以&;close&;将这个sub_lst追加到new_lst,然后用下一项初始化sub_lst。完成后,需要将sub_lst追加到new_lst后,因为这里的if语句中没有get。
下面是一个使用排序数组的简单方法:
NB。我在这里使用了严格的阈值,更新代码使用"<=">
def split(arr, k):
out = []
for i in sorted(arr):
if not out:
out = [[i]]
continue
if out[-1] and i-out[-1][0] < k: # use <= to accept equality
out[-1].append(i)
else:
out.append([i])
return out
的例子:
split([1,5,4,6,8,9,2], 3)
# [[1, 2], [4, 5, 6], [8, 9]]
split([1,13,6,8,9,3,5], 4)
# [[1, 3], [5, 6, 8], [9], [13]]
示例:
import random
k=10
random.seed(10)
randomList = []
listOfSublist = []
for i in range(0,10):
n = random.randint(1,100)
randomList.append(n)
print(randomList)
# uncomment this to test with the example
# randomList = [1,13,6,8,9,3,5]
# k = 4
randomList.sort()
print(randomList)
n = 0
for i in range(len(randomList)-1):
if randomList[i+1] - randomList[n] >= k: # when difference exceed k, create sublist
listOfSublist.append( randomList[n:i+1])
n=i+1
listOfSublist.append( randomList[n:len(randomList)]) # handle the end of the list
print(listOfSublist)
我相信有一个没有排序的解决方案,你可以通过在每一步删除你从随机列表中选择的数字来改善这一点,如果内存是一个问题。
输出:
[74, 5, 55, 62, 74, 2, 27, 60, 63, 36]
[2, 5, 27, 36, 55, 60, 62, 63, 74, 74]
[[2, 5], [27, 36], [55, 60, 62, 63], [74, 74]]