algorithm - 将数字分组到最接近的组

Question

例如，我有数字 46、47、54、58、60 和 66。我想以这样的方式对它们进行分组，以形成最大可能的组大小。如果数字的值在正负 10(含)以内，则数字会被分组。因此，根据您从哪个数字开始，对于此示例，可能存在三种可能的结果(如图所示)。

我想要的是第二种可能的结果，如果您从 54 开始就会出现这种情况，因为 44 到 64 之间的数字将被分组，留下 66 本身，并创建最大的组(5 项)。

我知道我可以很容易地暴力破解这个例子，但我确实有一长串数字，它需要对数千个数字执行此操作。任何人都可以告诉我我应该阅读的算法或给我建议吗？

Answer 1

您可以先简单地对数组进行排序。然后对于每个第 i 个数字，您可以进行二进制搜索以找到第 i 个数字 + 20 范围内最右边的数字，让最右边索引的位置为 X。您必须找到最大的 (X-i+1)对于所有第 i 个数字，我们就完成了 :)

运行时分析:该算法的运行时为 O(NlgN)，其中 N 是原始数组中的项数。

更好的解决方案:假设我们有数组 ar[] 并且 ar[] 有 N 项。

1. 按非降序排列 ar[]
2. 设置 max_result = 0，设置 cur_index = 0，i=0
3. 增加我，而我
4. 将 max_result 设置为 max(max_result,i-cur_index+1)
5. 设置cur_index=cur_index+1
6. 如果cur_index

运行时分析: O(N)，其中 N 是数组 ar[] 中的项目数，因为 cur_index 将恰好遍历数组一次，而 i 也将仅遍历一次。

正确性:因为数组是按非降序排列的，如果i < j和 j < k和 ar[i]+20 > ar[k]然后ar[j]+20 > ar[k]也。所以我们不需要检查这些已经检查过的项目。