algorithm - 在 O(n) 中运行的数组“最大差异”算法？

Question

给定一个包含 N 个整数的数组，对数组进行排序，并在排序后的数组中找出差值最大的 2 个连续数。

示例 – 在输入[1,7,3,2]输出上4（排序后的数组为[1,2,3,7]，最大差值为 7-3=4）。

算法 AO(NlogN)及时运行。

我需要找到一个功能与算法 A 相同的算法，该算法在 O(N) 时间内运行。

Answer 1

设数组为 X 并设 n = length(X)。将每个元素 x 放入桶号 floor((x - min(X)) * (n - 1) / (max(X) - min(X))) 中。每个桶的宽度是 (max(X) - min(X))/(n - 1) 并且最大相邻差异至少是那么多，所以有问题的数字最终会出现在不同的桶中。现在我们要做的就是考虑一对是桶 i 中的最大值，另一个是桶 j 中的最小值，其中 i < j 并且 (i, j) 中的所有桶 k 都是空的。这是线性时间。

证明我们确实需要地板：设函数为 f(X)。如果我们可以在线性时间内计算 f(X)，那么我们当然可以在线性时间内决定是否

0 < f(X) ≤ (max(X) - min(X))/(长度(X) - 1),

即，X 的元素是否均匀分布且不完全相同。令此谓词为 P(X)。P 的支持具有阶乘(length(X)) 连通分量，因此适用于代数计算模型的通常 Ω(n log n) 下限。

Answer 2

执行计数排序，然后扫描最大差异的结果。

由于连续数字要求，乍一看似乎任何解决方案都需要排序，这意味着最多 O( n log n )，除非您的数字范围受到足够的限制以进行计数排序。但如果是这样，你会以 O( n ) 获胜。

Answer 3

现在，首先试着想想如果你已经给出了 的最小值MIN和最大值MAX，那么在什么情况array下size N，最大间隙会是最小值和最大值？

显然，当所有元素都是MINor 或make 时，最大间隙将是最大MAX的maxgap = MAX - MIN。

MIN当所有元素在和之间等间距时，最大间隙将最小MAX。可以说它们之间的间距是间隙。

因此，它们排列为

MIN, MIN + gap, MIN + 2*gap, MIN + 3*gap, ... MIN + (N-1)*gap 
where

MIN + (N-1)*gap = MAX .

gap = (MAX - MIN) / (N - 1). 

所以，我们现在知道我们的答案将在range [gap, MAX - MIN]. 现在，如果我们知道答案不仅仅是 gap，我们所做的就是为 range 创建大小 gap 的桶。

[MIN, MIN + gap), [Min + gap, `MIN` + 2* gap) ... and so on

只会有(N-1)这样的桶。我们根据它们的值将数字放入这些桶中。

如果您从一个桶中选择任何 2 个数字，它们的差异将小于差距，因此它们永远不会有助于maxgap（记住maxgap >= gap）。我们只需要存储每个桶中的最大数和最小数，我们只看跨桶的数字。

现在，我们只需要按顺序遍历桶（它们已经按值排序），并得到至少一个值的前一个桶的 min_value 与 max_value 的差。我们取所有这些值的最大值。

int maximumGap(const vector<int> &num) {
    if (num.empty() || num.size() < 2) return 0;

    int maxNum = *max_element(num.begin(), num.end());
    int minNum = *min_element(num.begin(), num.end());

    //average gap from minNum to maxNum.
    int gap = (maxNum - minNum - 1) / (num.size() - 1) + 1;

    //number of buckets = num.size() - 1
    vector<int> bucketsMin(num.size() - 1, INT_MAX);
    vector<int> bucketsMax(num.size() - 1, INT_MIN);

    //put into buckets
    for (int i = 0; i < num.size(); i++) 
    {
        if (num[i] != maxNum && num[i] != minNum)
        {
            int buckInd = (num[i] - minNum) / gap;
            bucketsMin[buckInd] = min(bucketsMin[buckInd], num[i]);
            bucketsMax[buckInd] = max(bucketsMax[buckInd], num[i]);
        }
    }
    int maxGap = INT_MIN;
    int previous = minNum;

    for (int i = 0; i < num.size() - 1; i++) 
    {
        if (bucketsMin[i] == INT_MAX && bucketsMax[i] == INT_MIN) continue;   //empty
        //i_th gap is minvalue in i+1_th bucket minus maxvalue in i_th bucket
        maxGap = max(maxGap, bucketsMin[i] - previous);
        previous = bucketsMax[i];
    }
    maxGap = max(maxGap, maxNum - previous);
    return maxGap;
}

Answer 4

1. 找到最小值和最大值
2. k从数组中选择一个随机数
3. 通过将所有小于k左侧和大于k右侧的值放置来对算法进行排序。
4. 您知道两组的最小值和最大值，假设值在一条直线上，计算左组的间隙。对正确的组做同样的事情。
5. 与差距较大的组一起转到 2，您知道该组的最小值和最大值。执行此操作，直到所选组的值不超过 4 个。
6. 你现在有一个只有 4 个元素的组，排序并找到解决方案。

这是该算法如何工作的示例：

• 输入：9 5 3 4 12 9 31 17
• 选择随机数：k = 9
• 按较小和较大的 k 值排序
• 5 3 4 9 9 12 31 17，k 在索引 3 中
• 左组间隙 = (9 + 3) / (4 - 1) = 4
• 右组间隙 = (31 + 9) / (5 - 1) = 10
• 我们选择正确的组 9 9 12 31 17
• 选择随机数：k = 12
• 按较小和较大的 k 值排序
• 9 9 12 31 17，k 在索引 2 中
• 左组差距 = (12 + 9) / (3 - 1) = 11.5
• 右组间隙 = (31 + 12) / (3 - 1) = 21.5
• 12 31 17 中的最大间隙是 31 - 17 = 14

我的算法非常类似于选择算法，用于在线性时间内找到排序算法的 k 索引值。