ruby-on-rails - 获取数组内元素的距离？

Question

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

数组: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) 更好的性能。