尋找在數量

數組最接近的兩個元素之間的距離，所以我自學算法，這本書我買了，我有一個僞代碼用於查找的數字陣列兩個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

回答

相關問題