在一个数字数组中找到两个最近元素之间的距离。

Question

我正在自学一本关于算法的书籍，其中有一个伪代码可以用来查找数组中最接近元素之间的距离。

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

- user628796

---

你将dMin初始化为0，并用“//MaxInt”进行注释。你可以使用“Integer.MAX_VALUE”在Java中获取最大整数。 - Ethan

Answer 1

一个明显的效率提升方法：先对整数进行排序，然后你就可以查看相邻的数字。任何数字最接近它的邻居之一，要么是上面的，要么是下面的。

这将把复杂度从O(n²)降至O(n log n)。尽管对于所示的小值 n 来说，这不会产生显着的差异，但在理论复杂度方面，它很重要。

一个微小的优化是：使用一个局部变量来存储 Math.abs 的结果，那么如果该结果小于最小值，就不需要重新计算它了。或者，你可能希望使用 dMin = Math.min(dMin, Math.abs(a[i] - a[j]))。

请注意边界条件问题——如果允许负数，你的减法可能会溢出。

- Jon Skeet

---

因为他正在对整数进行排序，所以他可以进一步使用O(n)的排序算法，比如基数排序（Radix Sort）。 - stackoverflowuser2010

当你对数组进行排序时，如何找到最接近元素之间的距离？如果我们进行排序，我们只能找到哪两个元素彼此最接近。 - Barry

@Barry：离索引为i的项最近的邻居要么在索引i+1处，要么在索引i-1处 - 因此您可以轻松找到那个最接近的距离。然后，只需在数组上迭代以查找最小的“最接近距离”，如果您明白我的意思的话。 - Jon Skeet

Answer 2

这是一个O(n^2)的朴素解决方案。

更好的方式：

对数组进行排序，然后再次遍历它并检查排序后项之间的距离。
这可以工作，因为它们按升序排列，所以具有最接近值的数字是相邻的。

这个解决方案的时间复杂度为O(nlogn)。

- Yochai Timmer

---

使用库函数sort进行排序？ - user628796

库函数 sort 可能已经被很好地实现了。 - Yochai Timmer

Answer 3

首先，在追求速度之前，要保证正确性。为什么要用数组的长度来初始化 dmin 呢？如果数组是 [1, 1000]，你的算法的结果将是 2 而不是 999。

接着，为什么让 j 从 0 到数组的长度呢？这样每对元素都会被比较两次。你应该让 j 从 i+1 到数组的长度（这也会避免 i!=j 的比较）。

最后，你可以通过避免两次调用 Math.abs() 来节省几个纳秒。

此外，你可以完全改变你的算法，首先对数组进行排序，正如其他答案中所指出的那样。

- JB Nizet

Answer 4

您可以理论上通过以下步骤获得O(n)解决方案：

1. 使用基数排序进行排序(已编辑，感谢j_random_hacker指出)
2. 一次遍历以查找数字之间的差异

请注意保留HTML标记，但不要写任何解释。

- CMR

---

希尔排序不是O(n)。根据维基百科，最佳边界取决于所选择的间隔序列，但始终比O(nlog n)更差。也许你在想桶排序？ - j_random_hacker

@j_random_hacker，感谢您的指出。我已经修正了我的回答。user628796可以使用基数排序，因为问题空间都是数字。 - CMR

Answer 5

这里有一个问题：

如果数组已经排序，找到最小距离需要多长时间？

你应该能够从这里完成剩下的部分。

- corsiKa

Answer 6

排序数组在执行算法之前是必须的。

static int minDist(int arr[]) {
    int firstPointer, nextPointer;
    int minDistance = arr[1] - arr[0];
    int tempDistance;

    for (firstPointer = 0; firstPointer < arr.length; firstPointer++) {
        for (nextPointer = firstPointer + 1; nextPointer < arr.length; nextPointer++) {
            if (arr[nextPointer] == arr[firstPointer]) {
                return 0;
            } else {
                tempDistance = (arr[nextPointer] - arr[firstPointer]);
                if (minDistance > tempDistance) {
                    minDistance = tempDistance;
                }
            }

        }
    }
    return minDistance;
}

public static void main(String[] args) {
    int[] testArray = {1000, 1007, 3, 9, 21};
    Arrays.sort(testArray);
    int result = minDist(testArray);
    System.out.println(result); 
}

- Hany Omar

Answer 7

首先对数组进行排序可以免去使用另一个FOR循环。

    public static int distclosest(int numbers[]) {
       Arrays.sort(numbers);
       int aSize = numbers.length;
       int dMin = numbers[aSize-1];

       for(int i=0; i<aSize-1; i++) {
                dMin = Math.min(dMin, numbers[i+1]-numbers[i]);
       }
       return dMin;
    }

- Hari Ravilla

Answer 8

  static void MinNumber(int [] nums){

    Arrays.sort(nums);
    int min = nums[1] - nums[0]; 
    int indexOne = 0 , indexTwo = 1;

    for (int i = 1; i < nums.length -1; i++) {
        if (min > (nums[i+1] - nums[i])) {
            min = nums[i+1] - nums[i] ; 
            indexOne = i ; 
            indexTwo = i+1 ; 
        }
    }

    System.out.println("Minimum number between two values is: "+ min + " and the values is "+nums[indexOne]+" , "+nums[indexTwo] );

}

- hussam alhunaiti