在一个数组中找出元素之间的最小差值

Question

我有一个整数数组，其中包含一些有限数量的值。我的任务是找到数组中任意两个元素之间的最小差异。

请注意，该数组包含：

4, 9, 1, 32, 13

在这里，4和1之间的差异最小，因此答案是3。

应该如何设计算法来解决这个问题。另外，我不知道为什么，但我觉得使用树结构可以相对容易地解决这个问题。能做到吗？

- OneMoreError

---

最近点对问题是寻找在欧几里得空间中具有最小距离的两个点的问题。该问题是计算几何学中的一个经典问题，在计算机科学和工程学中也有广泛的应用。常见解法包括暴力搜索、分治法和随机化算法。最好的已知算法时间复杂度为O(n log n)。 - Rsh

你的意思是你正在解决这个问题 http://www.codechef.com/SEP12/problems/HORSES。 - nikhil

是的，我基于那个提出了这个问题！！ - OneMoreError

Answer 1

最小差值将是排序后连续对中的差异之一。对数组进行排序，遍历相邻数字对并寻找最小差值：

int[] a = new int[] {4, 9, 1, 32, 13};
Arrays.sort(a);
int minDiff = a[1]-a[0];
for (int i = 2 ; i != a.length ; i++) {
    minDiff = Math.min(minDiff, a[i]-a[i-1]);
}
System.out.println(minDiff);

这将打印 3。

- Sergey Kalinichenko

---

好的，我明白你的意思。但是排序本身需要O(n.log n)的时间。我只是好奇，我们能不能不排序！ - OneMoreError

如果您使用基数排序（radix sort），时间复杂度为*O(n)*。 - obataku

@CSSS 我认为你无法比 O(N*LogN) 更快地完成。你至少需要遍历一次数组中的元素，而且对于每个元素，你都需要找到它最佳的“对应项”以进行减法运算。如果你使用树，那么你能做到的最好性能是 Log(N)。 - Sergey Kalinichenko

请问您能否解释一下如何在这里使用树结构？！ - OneMoreError

从数组中遍历元素，并构建一个二叉搜索树。每次向BST添加一个节点时，检查新添加的元素与您在找到该元素在树中位置时遍历的每个节点之间的差异。具有最小差异的对应项将在这些节点中之一。将节点插入树需要Log(N)的时间复杂度，总时间复杂度为O(N*Log(N))。 - Sergey Kalinichenko

构建二叉搜索树实际上只是排序的另一种方式。 - Stephen C

Answer 2

您可以利用您正在考虑整数的事实来制定一个线性算法：

1. 第一遍扫描： 计算最大值和最小值
2. 第二遍扫描： 分配一个长度为（max-min+1）的布尔数组，初始值为false，并对数组中的每个值将（value-min）th值更改为true
3. 第三遍扫描： 计算布尔数组中真值条目的索引之间的差异。

- mookid

---

这在 N 方面是线性的，但也会对 max-min 产生线性依赖，这可能会导致效果很差。 - DarioP

Answer 3

虽然所有答案都是正确的，但我想展示负责n log n运行时间的潜在算法。使用“分治”方法找到两点之间的最小距离或在一维平面上找到最近的点。

一般算法：

• 令m为S的中位数。
• 将S分成S1, S2在m处。
• δ1 = Closest-Pair(S1).
• δ2 = Closest-Pair(S2).
• δ12是切口的最小距离。
• 返回δ = min(δ1、δ2、δ12)。

以下是我用Javascript创建的样例：

// Points in 1-D
var points = [4, 9, 1, 32, 13];

var smallestDiff;

function mergeSort(arr) {
  if (arr.length == 1)
    return arr;

  if (arr.length > 1) {
    let breakpoint = Math.ceil((arr.length / 2));
    // Left list starts with 0, breakpoint-1
    let leftList = arr.slice(0, breakpoint);
    // Right list starts with breakpoint, length-1
    let rightList = arr.slice(breakpoint, arr.length);

    // Make a recursive call
    leftList = mergeSort(leftList);
    rightList = mergeSort(rightList);

    var a = merge(leftList, rightList);
    return a;
  }
}

function merge(leftList, rightList) {
  let result = [];
  while (leftList.length && rightList.length) {
    // Sorting the x coordinates
    if (leftList[0] <= rightList[0]) {
      result.push(leftList.shift());
    } else {
      result.push(rightList.shift());
    }
  }

  while (leftList.length)
    result.push(leftList.shift());

  while (rightList.length)
    result.push(rightList.shift());

  let diff;
  if (result.length > 1) {
    diff = result[1] - result[0];
  } else {
    diff = result[0];
  }

  if (smallestDiff) {
    if (diff < smallestDiff)
      smallestDiff = diff;
  } else {
    smallestDiff = diff;
  }
  return result;
}

mergeSort(points);

console.log(`Smallest difference: ${smallestDiff}`);

- Suhail Gupta

Answer 4

我会把它们放在一个堆(heap)中，时间复杂度为O(nlogn)，然后一个一个地弹出并获取每个弹出的元素之间的最小差异。最终我将得到最小差异。不过，可能会有更好的解决方案。

- polerto

Answer 5

这实际上是一维的“最近点对”问题的重新表述。 https://zh.wikipedia.org/wiki/%E6%9C%80%E8%BF%91%E7%82%B9%E5%AF%B9%E9%97%AE%E9%A2%98 http://www.cs.umd.edu/~samir/grant/cp.pdf 正如下面引用的维基百科文章指出的那样，该问题的最佳决策树模型也需要在Ω(nlogn)时间内运行。

- Saket Mittal

Answer 6

分享最简单的解决方案。

function FindMin(arr) {

    //sort the array in increasing order

    arr.sort((a,b) => {
       return a-b;
    });

    let min = arr[1]-arr[0];

    let n = arr.length;

    for (var i=0;i<n;i++) {

      let m = arr[i+1] - arr[i];
      if(m < min){
        m = min;
      }
    }

    return m; // minimum difference.
  }

- dinesh_malhotra

Answer 7

对于那些正在寻找一行Python答案（或多或少），这里有两个可能的解决方案：

Python >= 3.10

l = sorted([4, 9, 1, 32, 13])
min(map(lambda x: x[1] - x[0], pairwise(l)))

从Python 3.10开始，您可以使用 pairwise（）函数来处理可迭代对象并返回所有连续的对。在我们对初始列表进行排序后，我们只需要找到差异最小的一对即可。

---

Python < 3.10

l = sorted([4, 9, 1, 32, 13])
min(map(lambda x: x[1] - x[0], zip(l[:-1], l[1:])))

在这种情况下，我们可以使用同一个列表的2个切片，并且使相邻元素成对，通过zip()方法重现¹pairwise()方法的行为。

---

_{1. pairwise() 的实际实现可能在空间方面更有效，因为它不需要创建列表的 2 个（浅层）副本。在大多数情况下，这应该是不必要的，但您可以使用 itertools.islice 在不创建副本的情况下迭代列表。然后，您将编写类似于 zip(islice(a, len(a) - 1), islice(a, 1, None)) 的东西。}

- Marco Luzzara

Answer 8

给定的问题可以在O(n)时间内轻松解决。看看我写的下面的代码。

    import java.util.Scanner;
    public class Solution {
    public static void main(String [] args) {
        Scanner input = new Scanner(System.in);
        int i, minDistance = 999999;
        boolean flag = false;
        int capacity = input.nextInt();
        int arr[] = new int[capacity];
        for (i = 0; i < capacity; i++) {
            arr[i] = input.nextInt();
        }

        int firstElement = input.nextInt();
        int secondElement = input.nextInt();

        int prev = 0;

        for (i = 0; i < capacity; i++) {
            if (arr[i] == firstElement || arr[i] == secondElement) {
                prev = i;
                break;
            }
        }

        for (; i < capacity; i++) {
            if(arr[i] == firstElement || arr[i] == secondElement) {
                if(arr[i] != arr[prev] && minDistance > Math.abs(i - prev)) {
                    minDistance = Math.abs(i - prev);
                    flag = true;
                    prev = i;
                } else {
                    prev = i;
                }
            }
        }

        if(flag)
            System.out.println(minDistance);
        else
            System.out.println("-1");
    }
}

- Pikachu

---

你的回答会更好，如果你解释一下算法背后的逻辑，而不是只提供没有任何解释的代码。 - Milos

Answer 9

在Python 3中，可以使用模块itertools来简化此问题，该模块提供了列表可用的组合。从该列表中，我们可以找到每个组合的总和并找到这些值中的最小值。

import itertools

arr = [4, 9, 1, 32, 13]

if len(arr) > 1:
    min_diff = abs(arr[0] - arr[1])
else:
    min_diff = 0

for n1, n2 in itertools.combinations(arr, 2): # Get the combinations of numbers
    diff = abs(n1-n2) # Find the absolute difference of each combination
    if min_diff > diff:
        min_diff = diff # Replace incase a least differnce found

print(min_diff)  

- Prakash S

---

虽然这可能回答了问题，但稍微解释一下可以提高答案的长期价值。 - jrook

@jrook 更新了答案并给出了解释。 - Prakash S

注释混合了“绝对差”和“总和最小值”。一个包含约len(arr)²个元素的列表以一种“非Python风格”的方式构建。 - greybeard

@老程序员 修改了答案，避免使用列表。这个怎么样？ - Prakash S

复杂度是多少？如果您检查所有组合，则为O(n^2)，因此比其他答案慢得多。 - Damien

Damien说得很对：时间复杂度为O(n²)（当min_diff变为0时可以停止）。不修改输入的情况下，一个救赎可能是O(1)的额外空间。 - greybeard