给定一个包含 N 个元素的数组，我们可以从 N 个元素中选择 K 个位置。但是我们需要以这样的方式选择 K 个位置，即如果我们取两个所选位置中的任何一个，比如 i 和 j，则比最小差值 (A[i ]-A[j])对于所有属于K个选择索引的i和j对应该尽可能大。
示例:
令 N=3 且数组 = [3 9 6 11 15 20 23 ] 且 K=3
那么这里的答案是 8，因为我们可以选择 [3,11,23] 或 [3,15,23]
我只想知道他们可以用某种贪心的方法来解决这个问题吗？还是 O(N) 或 O(N*log N) 之类的方法？
我知道它的蛮力解决方案。但我不认为将其张贴在这里是个好主意，因为它非常低效。
约束:
1 ≤ N ≤ 10^5
1 ≤ K ≤ 10^7
最佳答案
您可以对最大差值使用二分法来做到这一点。
首先对数组中的元素进行排序。
然后为最大差异选择一个值，我们称它为 D。
选择数组中最小的条目，然后遍历数组，直到我们与这个数字的距离达到 D，然后选择下一个数字。重复此操作，直到我们到达数组的末尾。
此过程将从数组中选择一定数量的值，这些值可能大于或小于 K。然后您使用 D 的二分法来找到 D 的最大值，该值允许您至少选择 K 个元素。
例如，对于 [3 6 9 11 15 20 23 ]，我们可能首先选择 5 的差异:
[3 6 9 11 15 20 23 ]
D=5: 3 9 11 20 => 4 chosen too high so increase D
D=10: 3 15 => 2 chosen too low so decrease D
D=8: 3 11 20 => 3 chosen
关于algorithm - 取K个元素，最大化最小距离，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/28812174/