获取数组内元素的距离？

Question

我正在努力完成一个相当简单的任务，它有一个非负整数数组，我需要在其中 return 最近的距离。

数组：arr = [8, 24, 3, 20, 1, 17]

解决方案：2、arr[2]-arr[4]

到目前为止，我只写了一个 O(n^2) 的解决方案，这显然不够好：

def smallest_distance(a)
  result = nil
  a.each_with_index do |item1, index1|
    a.each_with_index do |item2, index2|
      next if index1 == index2
      temp = (item1 - item2) >= 0 ? item1 - item2 : item2 - item1
      result = temp if result.nil? || temp < result
    end
  end
  result
end

关于如何改进这个的任何想法？

Answer 1

解决方法是对数组进行排序，然后迭代。您现在只需要检查相邻的候选项 (arr[i],arr[i+1])，而不是每对元素。

这在 O(NlogN) 中运行。

请注意，这是 Element Distinctness Problem 的泛化，因此如果您对最坏情况下的性能感兴趣，您无法获得比 O(NlogN) 更好的结果。

Answer 2

amit 发布的解决方案是正确的 n*log(n) 时间，这是找到解决方案所需的最快时间。他的解决方案的 ruby 代码看起来大致如下：

def smallest_distance(a)
  sorted = array.sort
  shortest = 999999 # arbitrary large value
  for i in 0..sorted.length
    comparison = sorted[i+1] - sorted[i] if sorted[i+1] != nil
    if comparison < shortest
      shortest = comparison
    end
  end
  return shortest
end

Answer 3

通常用于这种与数组相关的问题。如果你的算法等于或比 O(n^2) 差，你总是可以考虑使用排序算法来处理它。通常需要O(lgn)，那么之后你可能有一个线性算法。

对于这个问题，您可以对这个数组进行排序。然后只比较一个循环的相邻元素。最终结果时间复杂度是 O(n logn) 比你最初的想法要好。

所以你可以：

sorted = arr.sort

然后用一个循环copmare

arr[i] with ar[i+1]    from i = 0 ~ len-1

获取数组内元素的距离？

Get distance of elements inside an array?

algorithm

ruby-on-rails

time-complexity