我有一个数组 A = [a1, a2, a3, a4, a5...] 我想找到数组的两个元素,比如 A[i] 和 A[j] 使得i 小于 j和A [j]-A[i] 是最小且正的。
运行时间必须是 O(nlog(n))。
此代码是否可以完成这项工作:
首先对数组进行排序并跟踪每个元素的原始索引(即:原始(未排序)数组中元素的索引。
遍历排序数组并计算任何两个连续元素之间的差异,以验证较大元素的原始索引大于较小元素的原始索引的初始条件。
答案将是所有这些差异的最小值。
以下是这在示例中的工作方式:
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。