arrays - 查找数字数组中两个最近元素之间的距离

Question

com论坛，

我正在尝试在下面用 C++ 编译这个算法。请问有什么想法吗？

// Find the distance between the two closest elements in an array of numbers.
// Minimum Distance
// dmin = infinity;
// for i = (i to n - 2) do
// for j = i + 1 to n - 1 do
// temp = A[i] - A[j]
// if temp < dmin;
// dmin = temp;
// return dmin;

Answer 1

我建议您不要使用该算法（O(n^2)），而是对数字进行排序，然后进行线性扫描（O(nlogn)）。

Answer 2

是的，phant0m 是正确的，但是排序算法本身会使用循环。

排序算法通常以它们的效率来判断。在这种情况下，效率是指算法效率随着输入大小的增长而变大，并且通常基于要排序的元素数量。大多数使用的算法的算法效率为 O(n^2) 或 O(n*log(n))。(http://www.cprogramming.com/tutorial/computersciencetheory/sortcomp.html)

除非数组已经排序，或者您以后需要排序版本，或者您的数组可能变得非常大，否则您最好“咬紧牙关”并坚持原来的方法。