阵列和QUOT;最大差值＆QUOT;算法运行在O（n）的？ [英] Array "maximum difference" algorithm that runs in O(n)?

问题描述

给定N的整数，排序所述阵列的阵列，并找到2连续编号的有序数组的最大差异在。 实施例 - 在输入[1,7,3,2]输出4（排序后的数组是[1,2,3,7]，和的最大差为7-3 = 4）

Given an array of N integers, sort the array, and find the 2 consecutive numbers in the sorted array with the maximum difference. Example – on input [1,7,3,2] output 4 (the sorted array is [1,2,3,7], and the maximum difference is 7-3=4).

算法的运行在O（NlogN）的时间。

Algorithm A runs in O(NlogN) time.

我需要找到一个算法，在功能上等同于算法，运行在O（N）的时间。

I need to find an algorithm identical in function to algorithm A, that runs in O(N) time.

更新：

解决方案： 的http://cgm.cs.mcgill.ca/~godfried/teaching/dm-reading-assignments/Maximum-Gap-Problem.pdf

推荐答案

让阵列X和令n =长度（X）。把每一个元素x的桶数楼层（（X - 分（X））*（N - 1）/（MAX（X） - 分（X）））。每个桶的宽度（最大（X） - 最小（X））/（N - 1），最大相邻差至少多，所以有问题的数字风在不同的桶。现在我们要做的是考虑对，其中一个是最大的斗我，另一个是分斗Ĵ其中i＆LT; j和所有的桶K的（I，J）是空的。这是线性时间。

Let the array be X and let n = length(X). Put each element x in bucket number floor((x - min(X)) * (n - 1) / (max(X) - min(X))). The width of each bucket is (max(X) - min(X))/(n - 1) and the maximum adjacent difference is at least that much, so the numbers in question wind up in different buckets. Now all we have to do is consider the pairs where one is the max in bucket i and the other is the min in bucket j where i < j and all buckets k in (i, j) are empty. This is linear time.

证明我们真正需要的地板：让函数F（X）。如果我们能够计算函数f（x）的线性时间，那么可以肯定，我们可以以线性时间决定是否

Proof that we really need floor: let the function be f(X). If we could compute f(X) in linear time, then surely we could decide in linear time whether

0℃下F（X）与乐; （最大（X） - 最小（X））/（长度（X） - 1），

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

即是否X的元件被均匀地间隔开，而不是全部相同。让这个predicate为P（X）。 P的支持具有阶乘（长度（X））连接的部件，所以平时与欧米茄;（N日志N）的计算代数模型下界适用

i.e., whether the elements of X are evenly spaced and not all identical. Let this predicate be P(X). The support of P has factorial(length(X)) connected components, so the usual Ω(n log n) lower bounds for algebraic models of computation apply.

这篇关于阵列和QUOT;最大差值＆QUOT;算法运行在O（n）的？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！