algorithm - 给定一个实数列表。什么是将它们分组在一起以使组中的最大值和最小值小于 5 的好算法？

Question

假设我有一个这样的数字列表:1,100,2,10,3,14,55,101,102,58 我想要一个算法将它们组合在一起，这样

• 组数尽量少

• 一组内最大数与最小数之差应小于5。

其实第一个条件只是为了让问题更严谨；在我的应用程序中，数字相对分开，因此至少对于一个人来说很容易看到该组应该是什么样子。例如。在上面的例子中，它显然应该是 { [1,2,3],[10,14],[55,58],[100,101,102]}

有没有比双for循环更好的算法来解决这个问题？

谢谢!

Answer 1

我觉得你可以先把所有的数排序，然后在线性时间内贪婪地分组。假设您在名为 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)。