algorithm - 给出实数列表。有什么好的算法可以将它们组合在一起，以使组中的最大值和最小值小于5。

假设我有一个这样的数字列表：1100,2,10,3,14,55101102,58
我想要一个算法把它们组合在一起
组的数目应尽可能少
一组内最大数与最小数的差值应小于5。
事实上，第一个条件是要使问题更加严格；在我的应用程序中，数字相对来说是分开的，所以至少对于一个人来说，很容易看到这个组应该是什么样子例如，在上面的例子中，它显然应该是{[1,2,3]，[10,14]，[55,58]，[100101102]}
有没有比双for循环更好的算法来解决这个问题？
谢谢您！

最佳答案

我想你可以先把所有的数字分类，然后在线性时间内贪婪地组成一组。假设你有一个数组名为ARR，最大和最小元素之间的差异（即你在问题陈述中提到的5）被称为DIFF和数字数组的索引，从0开始。

n = len(arr)
sortedArr = sorted(arr)
groupStart = 0
groupsFound = [[sortedArr[0]]]
numGroups = 1
for i in range(1, n):
    if sortedArr[i] - sortedArr[groupStart] >= diff:
        groupStart = i
        numGroups += 1
        groupsFound.append([ sortedArr[i] ])
    else:
        groupsFound[numGroups-1].append(sortedArr[i])

我认为贪婪的方法是最优的，在这种情况下，因为每个数字必须在某个组中对于大小n的数组，排序数组的复杂性是O（nLogn），并且分组的复杂性是O（n），使得上面的代码的总体复杂度为O（nLogn）。