0

我有一个数组 A = [a1, a2, a3, a4, a5...] 我想找到数组的两个元素,比如 A[i] 和 A[j] 使得i 小于 jA [j]-A[i] 是最小且正的

运行时间必须是 O(nlog(n))。

此代码是否可以完成这项工作:

  1. 首先对数组进行排序并跟踪每个元素的原始索引(即:原始(未排序)数组中元素的索引。

  2. 遍历排序数组并计算任何两个连续元素之间的差异,以验证较大元素的原始索引大于较小元素的原始索引的初始条件。

  3. 答案将是所有这些差异的最小值。

以下是这在示例中的工作方式:

A = [0, -5, 10, 1]

在这种情况下,结果应该是 1 来自 和 之间的A[3]差异A[0]

  • 排序 A:newA=[-5,0,1,10]

  • 由于 OriginalIndex(-5)>OriginalIndex(0),不计算差异

  • 由于 OriginalIndex(1)>OriginalIndex(0),我们计算差 = 1

  • 由于 OriginalIndex(10)>OriginalIndex(1),我们计算差值 = 9

结果是最小差异,即 1。

4

2 回答 2

2

与另一篇文章中的主张相反,您的算法的运行时间不会有任何问题。例如,使用 heapsort 可以将数组排序O(n log n)为问题中给定的上限。沿着排序的数组额外O (n)运行一次不会再有任何损害,所以你仍然会继续使用 runtime O (n log n)

不幸的是,您的答案似乎仍然不正确,因为它没有给出正确的结果。

仔细查看给出的示例,您应该能够自己验证。您的示例中给出的数组是:A=[0,-5,10,1]

从 0 开始计数,选择​​索引i=2j=3满足给定的i < j要求2 < 3。计算A[j] - A[i]与所选值的差异归结为A[3] - A[2]计算1 - 10 = -9肯定小于1算法示例应用程序中计算的最小值。

于 2013-03-25T03:32:47.267 回答
1

由于您要最小化元素之间的距离,因此它们在排序列表中必须彼此相邻(如果它们不是,那么它们之间的元素与其中一个的距离将更短 -> 矛盾)。您的算法按照指定在 O(nlogn) 中运行,因此对我来说看起来不错。

于 2013-03-25T03:05:17.633 回答