从直线上的点中选取 "spread"
Picking the "spread" from the points on a line
我正面临一个算法问题，描述如下：给定一条从 0 到 N（非常大的 N）的直线，该直线上 X 点的列表，以及一个数字 Z（0<=Z<=X ) 从 X 中选取 Z 点以最大化两个最近点之间的距离。 O(n^2) 中的蛮力解决方案似乎并不难，但我正在寻找可以在 O(n log n) 时间内完成的更复杂的方法。非常感谢任何线索、解决方案和建议。
编辑：回答第一个问题post-它是必须最大化的最小距离（两个最近点之间）。
一种简单的方法是 O(XlogN)。
首先，对点进行排序。
接下来观察一下，如果您已经知道点之间的最小距离（称为 d），则需要 O(X) 来查看是否有一种方法可以选择 Z 点，所有这些点之间的距离至少为 d：取最左边的元素，然后是至少距离 d 的下一个元素，然后是至少距离 d 的下一个元素，依此类推。如果到数组末尾时你至少有 Z 个点，那么你就有了解决方案，如果没有，则没有解决方案。
现在，您可以在 [0, N] 上使用二进制搜索来找到具有解决方案的最大 d。
排序是O(XlogX)，二分搜索需要O(logN)次试验，每次都是O(X)。总体而言，这是 O(XlogX + XlogN)，但由于 N >= X 简化为 O(XlogN)。
我正面临一个算法问题，描述如下：给定一条从 0 到 N（非常大的 N）的直线，该直线上 X 点的列表，以及一个数字 Z（0<=Z<=X ) 从 X 中选取 Z 点以最大化两个最近点之间的距离。 O(n^2) 中的蛮力解决方案似乎并不难，但我正在寻找可以在 O(n log n) 时间内完成的更复杂的方法。非常感谢任何线索、解决方案和建议。
编辑：回答第一个问题post-它是必须最大化的最小距离（两个最近点之间）。
一种简单的方法是 O(XlogN)。
首先，对点进行排序。
接下来观察一下，如果您已经知道点之间的最小距离（称为 d），则需要 O(X) 来查看是否有一种方法可以选择 Z 点，所有这些点之间的距离至少为 d：取最左边的元素，然后是至少距离 d 的下一个元素，然后是至少距离 d 的下一个元素，依此类推。如果到数组末尾时你至少有 Z 个点，那么你就有了解决方案，如果没有，则没有解决方案。
现在，您可以在 [0, N] 上使用二进制搜索来找到具有解决方案的最大 d。
排序是O(XlogX)，二分搜索需要O(logN)次试验，每次都是O(X)。总体而言，这是 O(XlogX + XlogN)，但由于 N >= X 简化为 O(XlogN)。