排序算法:数组中的条件最小值

Question

我有一个数组A= a1，a2，a3，a4，a5.我想找到数组的两个元素，比如Ai和Aj，这样i小于j， array是最小的正。

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

这段代码能完成以下工作吗：

1. 首先对数组进行排序，并跟踪每个元素的原始索引(即:原始(未排序)数组中元素的索引。
2. 遍历排序数组，计算任意两个连续元素之间的差异，以验证大元素的原始索引大于小元素的原始索引的初始条件。
3. 答案将是所有这些差异的最小值。

下面是这个例子的工作原理：

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

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

• A类: newA=-5,0,1,10
• 由于OriginalIndex(-5)>原始指数(0)，所以不要计算差异
• 由于OriginalIndex(1)>原始指数(0)，我们计算差分=1
• 由于OriginalIndex(10)>原始指数(1)，我们计算了差值=9

结果是最小差，即1。

Answer 1

与另一篇文章中的声明相反，您的算法运行时不会有任何问题。例如，使用堆排序，数组可以在O(n log n)中排序，作为问题中的上限。沿排序数组运行一次的额外O (n)不会再对此造成损害，因此您仍然需要使用运行时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)中运行，所以在我看来很好。