查找与彼此距离最远的元素的子集

Question

我有一个我似乎无法弄清楚的面试问题.给定大小为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.

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

Answer 1

这可以使用DP在多项式时间内求解.

如上所述,第一步是对列表A进行排序.让X [i,j]成为从第一个i元素A中选择j个元素的解决方案.

现在,在k <= i时,X [i + 1,j + 1] = max(min(X [k,j],A [i + 1] -A [k])).

我将离开初始化步骤并记住子集步骤供您使用.

在您的示例(1,2,6,10)中,它按以下方式工作:

    1    2   6   10
1   -    -   -    -
2   -    1   5    9
3   -    -   1    4
4   -    -   -    1