小编cit*_*shi的帖子

我有一个我似乎无法弄清楚的面试问题.给定大小为N的阵列,找到大小为k的子集,使得子集中的元素彼此相距最远.换句话说,最大化元素之间的最小成对距离.

Example:

Array = [1,2,6,10]
k = 3

answer = [1,6,10]

强力方式需要找到大小为k的所有子集,这些子集在运行时是指数的.

我的一个想法是从数组中均匀分布值.我的意思是

1. 取第一个和最后一个元素
2. 找到它们之间的差异(在这种情况下为10-1)并将其除以k((10-1)/ 3 = 3)
3. 从两端向内移动2个指针,从前一个选择中挑选+/- 3的元素.所以在这种情况下,你从1和10开始,找到最接近4和7的元素.那就是6.

这是基于元素应尽可能均匀分布的直觉.我不知道如何证明它有效/无效.如果有人知道如何或有更好的算法,请分享.谢谢!