给定一个实数列表。什么是将它们分组在一起以使组中的最大值和最小值小于 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])

我认为贪婪的方法是最优的，在这种情况下，因为每个数字都必须在 some 组中。对于一个大小为n的数组，数组排序的复杂度为O(nlogn)，分组的复杂度为O(n)，使得上面代码的整体复杂度为O(nlogn).

Answer 2

我认为这在数学上没有明确定义。给定的最佳分组是什么，例如 numbers/elements [1, 8]？恕我直言，您需要定义一些对拆分进行评估的指标（或任何类型的评分函数）。例如，( [1, 2, 3], [4, 5, 6, 7, 8] ) 是否优于 ( [1, 2, 3, 4, 5], [6, 7, 8])？它们是否相等（在这种情况下选择哪个）？

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

Given a list of real numbers. What is a good algorithm to group them together so that the max and the min in the group is smaller than, say 5?

sorting

algorithm

computer-science