找到数字数组中两个最接近元素之间的距离
所以我从我购买的这本书中自学了算法，并且我有一个伪代码，用于查找数字数组中两个最简洁元素之间的距离
MinDistance(a[0...n-1]) Input: Array A of numbers Output: Minimum Distance between two of its elements dMin <- maximum integer for i=0 to n-1 do for j=0 to n-1 do if i!=j and | A[i] - A[j] | < dMin dMin = | A[i]-A[j] | return dMin 但是，我想对这个算法解决方案进行改进。 改变已经存在的东西，或者一起重写。 有人可以帮忙吗？ 我用Java编写函数和类来测试伪代码？ 那是对的吗？ 再一次，从效率的角度来看，我怎样才能做得更好。
//Scanner library allowing the user to input data import java.lang.Math.*; public class ArrayTester{ //algorithm for finding the distance between the two closest elements in an array of numbers public int MinDistance(int [] ar){ int [] a = ar; int aSize = a.length; int dMin = 0;//MaxInt for(int i=0; i< aSize; i++) { for(int j=i+1; j< aSize;j++) { dMin = Math.min(dMin, Math.abs( a[i]-a[j] ); } } return dMin; } //MAIN public static void main(String[] args){ ArrayTester at = new ArrayTester(); int [] someArray = {9,1,2,3,16}; System.out.println("NOT-OPTIMIZED METHOD"); System.out.println("Array length = "+ someArray.length); System.out.println("The distance between the two closest elements: " + at.MinDistance(someArray)); } //end MAIN } //END CLASS
所以我更新了函数以最小化调用Math.abs两次。 我还能做些什么呢？ 如果我要用sort重写它，它会改变我的for循环，还是理论上运行得更快就会一样。
public int MinDistance(int [] ar){ int [] a = ar; int aSize = a.length; int dMin = 0;//MaxInt for(int i=0; i< aSize; i++) { for(int j=i+1; j< aSize;j++) { dMin = Math.min(dMin, Math.abs( a[i]-a[j] ); } } return dMin; }
一个明显的效率改进：首先排序整数，然后你可以查看相邻的整数。 任何数字都将最接近其邻居向上或向下。
这将复杂性从O（n 2 ）改变为O（n log n）。 不可否认，对于n的小值显示它不会产生显着差异，但就理论复杂性而言，这很重要。
您可能想要进行一次微优化：使用局部变量来存储Math.abs的结果，如果结果小于最小值，则不需要重新计算它。 或者，您可能希望使用dMin = Math.min(dMin, Math.abs(a[i] - a[j])) 。
请注意，您需要注意边界条件 – 如果您允许负数，则减法可能会溢出。
这是O（n ^ 2）的天真解决方案。
更好的方法：
对数组进行排序，然后再次检查它并检查已排序项之间的距离。
这将起作用，因为它们按升序排列，因此具有最近值的数字是相邻的。
该解决方案将是O（nlogn）
首先，在快速启动之前，请将其设置为正确。 为什么用数组的长度初始化dmin ？ 如果数组是[1, 1000] ，算法的结果将是2而不是999。
那么，为什么让j从0到数组的长度？ 您将每对元素进行两次比较。 你应该使j从i + 1变为数组的长度（这也将避免i！= j比较）。
最后，通过避免两次调用Math.abs（），您可以获得几纳秒的时间。
然后，您可以通过首先对数组进行排序来完全更改算法，如其他答案中所述。
这是一个问题：
如果arrays被排序，找到最小距离需要多长时间？
你应该可以从这里完成rest。
理论上你可以得到一个O（n）解
- 使用
shell基数排序排序（编辑，感谢j_random_hacker指出） - 一遍找到数字之间的差异