查找数字数组中两个最接近的元素之间的距离 [英] Finding the distance between the two closest elements in an array of numbers
问题描述
所以我正在从我购买的这本书中教自己算法，并且我有一个伪代码来查找数字数组中两个最接近的元素之间的距离
So I'm teaching myself algorithms from this book I purchased, and I have a pseudo-code for Finding the distance between the two closetst elements in an array of numbers
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编写了函数和类来测试伪代码？那是对的吗？再一次，从效率的角度来看，我该如何做得更好。
However, I wanted to make improvements to this algorithmic solution. Change what's already there, or rewrite all together. Can someone help? I wrote the function and class in Java to test the pseudo-code? Is that correct? And once again, how can I make it better from efficiency standpoint.
//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
SO我更新了函数以最小化两次调用Math.abs，还有什么可以改进的呢，如果我要用sort重写它，它会根本改变我的for循环，还是从理论上讲会更快？
SO I updated the function to minimize calling the Math.abs twice. What else can I do improve it. If I was to rewrite it with sort, would it change my for loops at all, or would it be the same just theoretically run faster.
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;
}
推荐答案
效率明显提高：先对整数进行排序，然后再查看相邻的整数。任何数字都会向上或向下最接近其邻居。
One obvious efficiency improvement: sort the integers first, then you can look at adjacent ones. Any number is going to be closest to its neighbour either up or down.
这会改变O的复杂度（n 2 ）到O（n log n）。对于 n 的较小值，它不会产生明显的变化，但是就理论上的复杂性而言，这很重要。
That changes the complexity from O(n2) to O(n log n). Admittedly for the small value of n shown it's not going to make a significant difference, but in terms of theoretical complexity it's important.
您可能需要进行一次微优化：使用局部变量存储 Math的结果。 abs ，那么如果结果小于最小值，则无需重新计算。您可能想使用 dMin = Math.min（dMin，Math.abs（a [i]-a [j]））。
One micro-optimization you may want to make: use a local variable to store the result of Math.abs, then you won't need to recompute it if that turns out to be less than the minimum. Alternatively, you might want to use dMin = Math.min(dMin, Math.abs(a[i] - a[j])).
请注意，您需要注意边界条件-如果您允许使用负数，则减法可能会溢出。
Note that you need to be careful of border conditions - if you're permitting negative numbers, your subtraction might overflow.
这篇关于查找数字数组中两个最接近的元素之间的距离的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
