arrays - 算法奥林匹克：数组中的条件最小值

Question

我有一个数组 A = [a1, a2, a3, a4, a5...] 我想找到数组的两个元素，比如 A[i] 和 A[j] 使得i 小于 j和A [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。

Answer 1

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

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

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

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

Answer 2

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