如何找到包含n个数字的一 半的最小间隔？

Question

如果我有n个数字，我如何找到包含这些数字的一半的最小间隔[a，b]？

Answer 1

排序数字 设置left指数为0，right为n/2-1，得到差异A[right]-A[left] 在for循环中走n / 2步，递增两个索引，再次计算差异，记住最小的索引和相应的索引。

Answer 2

对数字进行排序并计算所有差异A[i+n/2] - A[i]。解决方案由最小化差异的指数给出。

---

说明：

不需要在包含少于n / 2个数字的区间（因为它们不满足条件）中搜索，也不需要在包含更多元素的区间中搜索（因为如果找到合适的区间，它将不会是最小的，因为你可以删除极端元素）。

对元素进行排序时，数组中的任何序列都以其第一个和最后一个元素为界。因此，对数字进行排序并滑动n / 2个元素的窗口就足够了。

---

现在判断这种O（n log n）方法是否最优是更具挑战性的。

Answer 3

以下怎么样？

• 按升序对给定的数字序列进行排序。
• 用i从第1到第（[n / 2]）个数字开始循环
• 计算i +（[n / 2]）th和第i个之间的差值d。将数字i，i + [n / 2]和d存储在可迭代的集合arr中。
• 结束循环
• 从数组arr中找到d的最小值。对应于此d的i和i + [n / 2]的值是您的最小范围。