运行在O(n)内的数组“最大差”算法？
给定一个由N个整数组成的数组，对该数组进行排序，并在排序后的数组中找到差值最大的两个连续数字。
示例- on input [1,7,3,2] output 4 (排序数组为[1,2,3,7]，最大差值为7-3=4)。
算法A在O(NlogN)时间内运行。
我需要找到一个在功能上与算法A相同的算法，运行时间为O(N)。
回答 4
Stack Overflow用户
发布于 2012-04-22 05:51:19
设数组为X，n= length(X)。将每个元素x放入bucket number floor((x - min(X)) * (n - 1) / (max(X) -min(X)。每个存储桶的宽度是(max(X) - min(X))/(n - 1)，相邻的最大差值至少也是这个数字，所以所讨论的数字最终会出现在不同的存储桶中。现在我们要做的就是考虑成对，其中一个是桶i中的最大值，另一个是桶j中的最小值，其中i
证明我们真的需要floor:假设函数是f(X)。如果我们可以在线性时间内计算f(X)，那么我们当然可以在线性时间内决定
0< f(X)≤(max(X) - min(X))/(length(X) - 1)，
即，X的元素是否均匀分布并且不是全部相同。设此谓词为P(X)。P的支持具有阶乘(长度(X))连通分量，因此通常的计算代数模型的Ω( lower )下界适用。
Stack Overflow用户
发布于 2012-04-22 05:09:36
执行，然后扫描结果，找出最大的差异。
由于需要连续的数字，乍一看似乎任何解决方案都需要排序，这意味着最多是O(n log n)，除非您的数字范围对于Counting排序有足够的限制。但如果是这样，你就会以O(n)取胜。
Stack Overflow用户
发布于 2019-08-12 05:43:12
现在，首先试着想一想，如果你已经在array of size N中得到了最小值MIN和最大值MAX，那么在什么情况下最大差距会是最小值和最大值？
显然，当所有元素都是MIN或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，那么我们所做的就是为范围创建大小为gap的桶。
[MIN, MIN + gap), [Min + gap, `MIN` + 2* gap) ... and so on只会有(N-1)这样的存储桶。我们根据它们的值将数字放入这些桶中。
如果你从单个存储桶中选择任意两个数字，它们的差异将小于gap，因此它们永远不会对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;
}https://stackoverflow.com/questions/10262937
复制相似问题
腾讯云开发者
