从给定的范围内求出一个数字的最大最小差

Question

假设我有一个N个数的数组{A1，A2，.，An}和2个数字P，Q

我必须在P和q之间找到一个整数M，这样，最小{\-Ai}，1≤i≤N}是最大的。

1

用简单的话说：

对于每个数字，找出这个数字和数组之间的最小绝对差。然后，在所有这些最小差异中，找出最小差最大的数。

我必须在O(NlogN)或更短的时间内这样做。

我尝试了以下几点：

• 数组A (NlogN)的排序
• 迭代P和Q之间的所有数字，并对每个数使用改进的二进制搜索找到最小差，并跟踪谁的差异最大- O((Q-P)logN)

我猜有某种数学“把戏”，比如用我错过的平均值.

编辑(添加示例)：

例如，如果数组{5814}和P=4 Q=9

答案是4,6,7或9。

让我们看看数字4-9。

|4-5| = 1
|4-8| = 4
|4-14| = 10

所以4的最小差是1

|5-5| = 0
|5-8| = 3
|5-14| = 9

所以4的最小差是0。

我们继续寻找所有数字的最小差，然后我们需要知道哪个数(4/5/6/7/8/9)的最小差最大(在本例中，4、6、7和9有一个最小差，即所有最小差中的最大值)。

Answer 1

首先，必须对数组进行排序。然后您必须注意到，您的解决方案要么是P，要么是Q，或者是某个点x[i] = (A[i] + A[i+1]) // 2。基本上，xi在数组中的连续元素之间处于中间(如果这个xi介于P，q之间)。

因为N非常小，所以它基本上在O(1)中运行。