在数组中寻找条件极小差异的算法

-2

假设你有一个不同整数的数组：A = [a1，a2，a3，a4，a5 ...] 我需要找到数组的两个元素，比如A [ i]和A [j]，使得i小于j并且A [j] -A [i]是最小的。在数组中寻找条件极小差异的算法

下面是一个有效的解决方案吗？

阵列首先排序，并保持每个元素的原始索引（即，轨道：所述元件的原件中的索引（未排序）阵列
经过排序后的数组，并计算任何之间的差异该验证的初始条件，即更大的元素的原始索引小于更小的元素的原始索引更大两个连续的元件。
答案将是所有这些不同的最小值。

这里是这对于前者如何工作？充足的：

A=[0,-5,10,1] (in this case the result should be 1 coming from the difference between  A[3] and A[0]) 
sort A : newA=[-5,0,1,10] 
since OriginalIndex(-5)>OriginalIndex(0), do not compute the difference 
since OriginalIndex(1)>OriginalIndex(0),we compute the difference =1 
since OriginalIndex(10)>OriginalIndex(1), we compute the difference =9 
The result is the minimal difference, which is 1

来源

2013-03-25 user2205925

你的第一句话是不完整的。 – eliot 2013-03-25 01:47:08

谢谢艾略特我现在修好了。任何线索，如果这种方法可能工作？ – user2205925 2013-03-25 02:04:24

如果对输入进行排序：[ - 1,0,2,10]，则取前两个元素：-1和0.在前面，未排序的数组-1是AFTER 0，所以初始条件“i is less比j和A [j] -A [i]最小“未被验证，因为我比j大。然后你移动到0和2，差别是2.这是我们有效的区别，因为元素2是未排序数组中的元素1之后的元素。然后你移动到2和10，差异是8.找到的最小差异是2，所以这是答案。你怎么看？ – user2205925 2013-03-25 02:41:10

这是一个解决方案，它是O（n^2）在时间上，但O（1）在空间。在伪代码：

for i = 0; i < array.length; i++ 
    for j = i + 1; j < array.length; j++ 
     if a[j] - a[i] < min 
      min = a[j] - a[i] 
return min

来源

2013-03-25 02:06:07

这需要O（n^2），我在寻找O（nlog（n）），有什么想法？ – user2205925 2013-03-25 03:04:13

如果你想找到什么是积极的最小差异，那么基本上，你的问题是：

Find two closest elements in an array.

的O（nlogn）的解决方案很简单：

sort - O（nlogn）
获取两个相邻元素之间的差异并找到最小的一个 - O（n）

所以整体运行时间为O（nlogn）

你不必在意指数。因为你什么是abs(A[i]-A[j])=abs(A[j]-A[i])，没关系i>j或j>i

来源

2013-03-25 02:45:28 gongzhitaao

你说的是对的。然而，就这个问题而言，我只是在两个元素之间寻找最小差值A [j] -A [i]，以验证初始条件j> i（在初始数组中）。我的算法看起来好吗？ – user2205925 2013-03-25 03:15:57

@ user2205925不是。因为你跳过一些潜在的答案，因为“i> j”或“j> i”，这实际上并不重要。例如''[1,0,3,5]'' – gongzhitaao 2013-03-25 03:18:44

我的意思是说，如果我不是在寻找绝对最小差异，而是验证条件i user2205925 2013-03-25 03:24:20

在数组中寻找条件极小差异的算法

回答

相关问题