3

例如，我有数字 46、47、54、58、60 和 66。我想对它们进行分组，以使组大小尽可能大。如果数值在正负 10（含）范围内，则数字将被分组。因此，根据您从哪个数字开始，对于此示例，可能存在三种可能的结果（如图所示）。

我想要的是第二种可能的结果，如果你从 54 开始，就会发生这种情况，因为 44 到 64 之间的数字将被分组，单独留下 66，并创建最大的组（5 个项目）。

我意识到我可以很容易地暴力破解这个例子，但我真的有一个很长的数字列表，它需要在数千个数字中做到这一点。谁能告诉我我应该阅读的算法或给我建议？

在此处输入图像描述

4

2 回答 2

2

您可以简单地先对数组进行排序。然后对于每个第 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 < j然后j < k也是。所以我们不需要检查那些已经检查过以前项目的项目。ar[i]+20 > ar[k]ar[j]+20 > ar[k]

于 2013-08-07T17:17:53.437 回答
0

这就是我想做的。对不起，我没有很好地解释自己。每次迭代都使用删除前一个最大组后剩下的数字来找到最大的可能组。Matlab代码：

function out=groupNums(y)
d=10;
out=[];
if length(y)==1
    out=y;
    return
end
group=[];
for i=1:length(y)
    group{i}=find(y<=y(i)+d & y>=y(i)-d);
end
[~,idx]=max(cellfun(@length,group));

out=[out,{y(group{idx})}];
y(group{idx})=[];
out=[out,groupNums(y)];
于 2013-08-07T17:50:31.960 回答