给定一个包含 N 个整数的数组，将该数组排序，并找到排序后相邻两个数之间差值最大的一对。
例如：对于输入的数组[1,7,3,2]，输出4（排序后的数组为[1,2,3,7]，最大差值为 7-3=4）。
算法A的时间复杂度为O(NlogN)。
我需要寻找一种与算法A功能相同的算法，但时间复杂度为O(N)。
4个回答
15
将数组X命名为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)之间的所有桶都为空。这是线性时间。
证明我们确实需要floor：令函数为f(X)。如果我们可以在线性时间内计算f(X)，那么我们肯定可以在线性时间内决定
0 < f(X) ≤ (max(X) - min(X))/(length(X) - 1)，
即X的元素是否均匀分布并且不完全相同。让这个谓词为P(X)。P的支持有阶乘(length(X))个连通组件，因此对于计算模型的代数模型，通常的Ω(n log n)下限适用。
- zxc
3
谢谢解释，我想理解最后一句话。假设这个谓词是P（X）。P的支持有阶乘（length（X））个连通分量，因此对于计算的代数模型，通常的Ω（n log n）下限适用。更好的方法。除非我建立不变量规则，否则我很难解决问题，我觉得这可能有助于我更好地解释这个问题，即使我直观地理解“如何”它工作。 - Sid
如果
B[0...n-2]是n-1个桶，那么您还需要考虑对(min(X), min(B[0]))和(max(X), max(B[n-2]))这两对的处理。 - Raghubansh Mani如果没有空的桶怎么办？那么 {k | k∈(i,j) and size(k) = 0} = ∅。那我们该怎么办？ - Sriman
4
执行计数排序，然后扫描结果以找到最大差异。
由于连续数字的要求，乍一看似乎任何解决方案都需要排序，这意味着最好情况下是O(n log n)，除非您的数字范围足够受限以进行计数排序。但如果是这样，您将获得O(n)的胜利。
- DigitalRoss
4
正如OJ所指出的那样，基数排序应该也可以解决这个问题。我一直很喜欢基数排序，但不幸的是大多数问题似乎都涉及字符数据... - DigitalRoss
是的，在正常的现实情况下它可以工作，但在这个任务中整数范围并没有限制。我想这可以完全不用排序就能完成。 - daremy
它始终是O(n)，检查我的解决方案。 - Ilya Gazman
乍一看，似乎任何解决方案都需要排序，但仔细检查后，情况并非如此。 - greybeard
0
现在，首先尝试想一想，如果您已经在大小为N的数组中给出了最小值MIN和最大值MAX，在什么情况下最大间隙会最小或最大？
显然，当所有元素都是MIN或MAX时，最大间隙将达到最大值，使得maxgap = MAX - MIN。
当所有元素在MIN和MAX之间等间隔排列时，最大间隙将达到最小值。假设它们之间的间隔是gap。
因此，它们被排列为
MIN, MIN + gap, MIN + 2*gap, MIN + 3*gap, ... MIN + (N-1)*gap
where
MIN + (N-1)*gap = MAX .
gap = (MAX - MIN) / (N - 1).
所以，我们现在知道答案将在范围 [间隙，MAX - MIN]内。现在，如果我们知道答案大于间隙，我们要做的是为范围创建大小为间隙的桶。
[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;
}
- Visluck
-1
- 找到最小值和最大值
- 从数组中随机选择一个数字
k - 通过将所有小于
k的值放在左边，大于k的值放在右边来排序算法。 - 你知道两个组的最小值和最大值，假设这些值在一条直线上，计算左侧组的间隙。对于右侧组也是如此。
- 选择具有更大间隙的组并执行步骤2，你知道该组的最小值和最大值。重复此过程，直到所选组的值不超过4个。
- 现在你得到了一个只有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索引值。
- Ilya Gazman
3
这个算法看起来非常不直观，很难从逻辑上理解。您能否详细说明一下您的思考过程/方法背后的灵感？ - user248884
代码出了问题。我们选取数组中的数字9，结果得到的是同样的数组，只是在9处被分成了两部分，9属于右侧。左“间隙”为0，小于右侧“间隙”，（14+9）/5=5。我们选择了右侧组，并且永远也找不到所需的最大间隙，即-8和8之间的间隙。 - Gulzar
为什么平均间隔更大的一半会有最大的间隔差距？ - greybeard
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接
[1,9,2]。在这种情况下，基数排序或计数排序不是正确的方法。 - user248884