algorithm - 未排序数组中的最大间隙

Question

我从这里遵循算法:

http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf

我不明白第 2 步和第 3 步:

2. Divide
 the
 interval
 [x­min,
x­max] 
into
(n−1)
 "buckets"
 of
 equal
size
 delta= (x­max
–
x­min)/(n‐1)

3. For
 each 
of 
the 
remaining 
(n‐2) 
numbers 
determine
 in 
which 
bucket it 
falls
 using 
the 
floor
 function. 
The 
number 
xi 
belongs 
to 
the 
kth
 bucket 
Bk
 if, 
and 
only 
if, 
(xi
‐
x­min)/δ
=
k‐1.


让我们说a = [13, 4, 7, 2, 9, 17, 18]

最小值:2 最大值:18 n-1:6。所以我的桶数将是 6。delta = (18-2)/6 = 2。那是 6 个桶每个元素都有 2 个元素。 (我总共可以拥有 12 个元素)

第 2 步:问题:如果只有 12 个元素，我的最大 18 个元素在哪里？

第 3 步。对于元素 18:根据算法，它应该在 math.floor((17-2)/float(2)) = 7所以 18 应该在第 8 个 block 中，但是我们只有 (n-1) = 6 个桶。

对我来说是个谜!

编辑1:对不起第 3 步:错误的数学:数学.floor((17-2)/float(2)) = 5仍然需要弄清楚最小值和最大值在哪里。

编辑2:根据 Miljen Mikic 的回答:他是对的，我的问题是“我们用最大值和最小值做什么”在第 6 步中:

In
 L
 find 
the 
maximum
 distance
 between
 a 
pair 
of 
consecutive
 minimum
 and
maximum
(xi­max,
xj­min), 
where 
j
>
i.


j > i 怎么来的？即下一个桶的最大值和当前桶的最小值。

Answer 1

在您引用的算法中，您没有将最小值和最大值放入桶中。注意第五步后的注意事项:

Note: Since there are n-1 buckets and only n-2 numbers..

如果您将最小值和最大值放入某些桶中，那么您将得到 n 个数字，而不是 n-2。现在真正的问题是:如何处理最小值和最大值？实际上，算法的第 6 步应该更清楚一点。当你检查列表 L 时，你应该从 x-min 开始并将它与 x1-min 进行比较，最后你应该比较 x(n-1 )-max 和 x-max，因为最大间隙实际上可以包括最小值或最大值，例如在这个例子中:[1,7,3,2]。当然，这两个额外的比较仍然是线性时间复杂度。

请注意，您可以通过将最小值和最大值放入桶中来稍微更改算法(通过完全相同的公式!)然后您将得到 n 数字和 n 水桶。为什么？最小值总是放在第一个桶中(见公式)，最大值需要放在第 n 个桶中，这在以前不存在，所以如果我们应用此更改，我们就会有一个额外的桶.这意味着在这种情况下你不能总是应用鸽洞原则，但它仍然认为一对连续元素之间的最大距离必须至少是桶的长度。怎么会？如果至少一个桶包含两个元素，那么一定有一些空桶，这是很清楚的。否则，所有桶只包含一个元素；这意味着第一个桶包含最小值，第二个桶包含一个值至少为 x_min + δ 的元素，因此该元素与 x_min 的差值为least δ，桶的长度。为什么第二个桶中的元素必须至少为 x_min + δ？如果它小于那个，例如如果它是 x_min + δ - k，其中 k > 0，那么它也属于第一个桶，因为 [((x_min + δ - k) - x_min)/δ] = [(δ - k)/δ] = 0，即不是我们假设的秒!