寻找在数量

数组最接近的两个元素之间的距离，所以我自学算法，这本书我买了，我有一个伪代码用于查找的数字阵列两个closetst元件之间的距离寻找在数量

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两次。我还能做些什么来改善它。如果我要重新编写它，是否会改变我的循环，或者只是理论上运行得更快。

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; 
    }

来源

2011-02-22 user628796

您将dMin初始化为0，并用“// MaxInt”对其进行注释。您可以通过“Integer.MAX_VALUE”获得java中的最大整数。 – Ethan 2016-02-10 18:15:26

一个明显的效率改进：首先对整数进行排序，然后您可以查看相邻的整数。任何数字都将与其邻居最近或最近。

这将复杂度从O（n ）更改为O（n log n）。不可否认的是，n的小数值表明它不会产生显着差异，但从理论上的复杂性来看，这很重要。

您可能想要进行的一个微优化：使用局部变量来存储Math.abs的结果，如果结果小于最小值，则不需要重新计算它。或者，您可能要使用dMin = Math.min(dMin, Math.abs((a[i] - a[j]))。

请注意，你需要小心的边界条件 - 如果你允许使用负数，您减法可能溢出。

来源

2011-02-22 19:18:52

由于他正在整理整数，他可以进一步使用排序算法（如排序算法）。 – stackoverflowuser2010 2011-02-22 19:25:13

http://en.wikipedia.org/wiki/Element_distinctness_problem – 2011-02-22 19:27:21

如何在排序数组时排列最接近的元素之间的距离？如果我们正在排序，我们所能找到的是哪两个元素彼此最接近。 – Barry 2011-12-14 03:44:27

这里有一个问题：

它需要多长时间找到最小距离，如果阵列排序？

您应该能够从这里完成剩下的。

来源

2011-02-22 19:19:18 corsiKa

这是为O的幼稚溶液（N^2）。

更好的办法：

排序数组，然后去了它一次，并检查所有排序项之间的距离。
这工作，因为他们是按升序排列，因此与最近值的数量是相邻的。

该解决方案将是O（nlogn）

来源

2011-02-22 19:22:55

首先，使其快速，使其正确的之前。为什么用数组长度初始化dmin？如果数组是[1, 1000]，算法的结果将是2而不是999.

那么，为什么要让j从0到数组的长度？你比较每一对元素两次。你应该让j从i + 1跳到数组的长度（这也会避免i！= j比较）。

最后，你可以通过避免调用Math.abs（）两次获得几纳秒。

然后，您可以通过首先对数组进行排序来完全更改算法，如其他答案中所述。

来源

2011-02-22 19:27:29

理论上可以得到O（n）的

解决方案与外壳基数排序（编辑，感谢j_random_hacker指点出来）
一个传球之间找到差异排序号码

来源

2011-02-22 19:28:31 CMR

回答

相关问题