我面临一个算法问题，描述如下：给定一条从0到n（真的大N），在该行上的X点的列表，和一个Z（0＜z＝＝x）从x取z点，以最大化两个最近点之间的距离。o（n^2）中的蛮力解决方案似乎没有那么困难，但我正在寻找更复杂的方法，可以在o（n logn）时间内完成。任何线索，解决方案，建议都非常感谢。
编辑：回答第一个帖子中的问题，这是必须最大化的最小距离（在两个最接近点之间）。
最佳答案
一个简单的方法是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）。