arrays - k 大小的子序列中差异的最大值

Question

给定 n 个元素的排序序列。从长度为 k 的子序列的所有差分对中找出所有最小值的最大值。

Here 1<=n<=10^5
and 2<=k<=n

For eg: [2, 3, 5, 9] and k = 3
there are 4 subsequences:

[2, 3, 5] - min diff of all pairs = 1
[2, 3, 9] - min diff of all pairs = 1
[3, 5, 9] - min diff of all pairs = 2
[2, 5, 9] - min diff of all pairs = 3

所以答案是所有最小差异的最大值 = 3

天真的方法是找到所有 k 个长度的子序列，然后在每个子序列中找到最小值，然后在所有子序列中找到最大值，但由于限制，这会超时。

除此之外，我的想法是找到最佳距离的序列，以便最小值变为最大值。

有人能给出最优更好的解决方案吗？

Answer 1

假设您的整数序列是a[i]。然后我的解决方案将及时找到答案 O(n log((a[n-1]-a[0])/n))。如果您的序列是 float ，它可能会在相似的时间内运行，但理论上可能与 O(n^3) 一样糟糕。

关键的观察是这样的。从最小间隙至少为 m 的第一个元素开始构造最紧凑的序列很容易。只取第一个元素，当它至少比你取的最后一个元素大 m 时互相取一个。所以我们可以编写一个函数来构建这个序列并跟踪 3 个数字:

1. 我们得到了多少个元素
2. 我们找到的最小间隙的大小。
3. 下一个最小的 m 会导致更紧凑的序列。也就是说，与我们未包含的元素的最大差距。

对于您的序列，如果我们以 2 的间隙执行此操作，我们会发现我们采用了 3 个元素，最小间隙为 3，如果我们寻找的间隙为1.

这些信息足以构建所需间隙长度的二分搜索。关键逻辑如下所示:

lower_bound = 0
upper_bound = (a[n-1] - a[0])/(k-1)
while lower_bound < upper_bound:
    # Whether int or float, we want float to land "between" guesses
    guess = (lower_bound + upper_bound + 0.0) / 2
    (size, gap_found, gap_different) = min_gap_stats(a, guess)
    if k < size:
        # We must pick a more compact sequence
        upper_bound = gap_different
    else:
        # We can get this big a gap, but maybe we can get bigger?
        lower_bound = gap_found

如果我们为您的序列运行此程序，我们首先将 lower_bound 设置为 0 并将 upper_bound 设置为 7/2 = 3(感谢整数除法)。我们会立即找到答案。

如果您有一系列具有相同值的 float ，则需要更长的时间。我们将首先尝试 3.5，并在 3 处获得一个具有不同决策的序列 2。然后我们将尝试 1.5，并找到具有我们想要的间隙的序列 3。

二分查找通常会进行对数次的遍历。 然而，每次我们将上限或下限设置为实际成对间隙的大小。由于只有 O(n^2) 间隙，我们保证只需要那么多遍。