我有一个面试问题，我似乎无法弄清楚。给定一个大小为 N 的数组，找到大小为 k 的子集，使得子集中的元素彼此相距最远。换句话说，最大化元素之间的最小成对距离。
Example:
Array = [1,2,6,10]
k = 3
answer = [1,6,10]
暴力方式需要找到大小为 k 的所有子集，k 在运行时呈指数增长。
我的一个想法是取数组中均匀分布的值。我的意思是
- 取第一个和最后一个元素
- 找出它们之间的差（在本例中为 10-1）并将其除以 k ((10-1)/3=3)
- 从两端向内移动 2 个指针，选出与之前选取的元素相差 +/- 3 的元素。因此，在本例中，您从 1 和 10 开始，找到最接近 4 和 7 的元素。那就是 6。
这是基于元素应尽可能均匀分布的直觉。我不知道如何证明它有效/无效。如果有人知道如何或有更好的算法，请分享。谢谢！
这可以使用 DP 在多项式时间内求解。
正如您所提到的，第一步是对列表 A 进行排序。令 X[i,j] 为从前 i 个元素 A 中选择 j 个元素的解决方案。
现在，X[i+1, j+1] = max( min( X[k,j], A[i+1]-A[k] ) ) 在 k
我将把初始化步骤和子集步骤的记忆留给您进行。
在您的示例 (1,2,6,10) 中，它的工作方式如下：
1 2 6 10
1 - - - -
2 - 1 5 9
3 - - 1 4
4 - - - 1
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
