1. 概述
在本篇文章中，我们将介绍如何在一个数值数组中找到两个具有最小绝对差值的元素。这是在处理排序、去重、数据压缩等场景时常见的问题。
2. 最小差值定义
我们有一个数值数组 a = [a₁, a₂, ..., aₙ]，目标是找出其中两个差值最小的元素。
举个例子，如果 a = [1, 5, 31, 7, 11]，那么最小的绝对差值出现在 5 和 7 之间，所以我们的算法应输出 (5, 7) 这一对。
3. 解法思路
假设我们已经将数组 a 排序为非递减顺序：a₁ ≤ a₂ ≤ ... ≤ aₙ。那么，对于每个 aᵢ 来说，离它最近的数只能是它前一个或后一个元素。
换句话说，只要数组是排序过的，最小差值一定出现在相邻元素之间。
因此，我们可以：
- 对数组排序；
- 遍历数组，比较相邻元素的差值；
- 找出最小的差值对。
例如，将 a = [1, 5, 31, 7, 11] 排序后得到 [1, 5, 7, 11, 31]，相邻元素差值为 [4, 2, 4, 20]，最小差值出现在 5 和 7 之间。
3.1 伪代码实现
algorithm FindTwoClosestNumbers(a):
// INPUT
// a = an array of n numbers
// OUTPUT
// (p, q) = a pair with the minimal absolute difference in a
a <- sort a
(p, q) <- (a[1], a[2])
for i <- 3 to n:
if |a[i-1] - a[i]| < |p - q|:
(p, q) <- (a[i-1], a[i])
return (p, q)
3.2 时间复杂度分析
整个算法的时间复杂度主要取决于排序部分：
- 如果使用归并排序（Merge Sort），最坏情况下的时间复杂度是
O(n log n)； - 如果使用快速排序（Quicksort），平均情况下是
O(n log n)，但最坏情况是O(n²)； - 查找相邻差值的部分是
O(n)，不影响整体复杂度。
所以，整个算法的时间复杂度为 O(n log n)。
⚠️ 虽然快速排序最坏情况是 O(n²)，但在实际应用中通常比归并排序更快，因为其常数因子更小。
4. Rabin 随机算法（一维）
如果我们追求更优的时间复杂度，可以考虑使用 Rabin 的随机算法。该算法在概率意义上能达到 线性时间复杂度。
4.1 核心思想
核心思想是通过随机采样来估计最小差值 δ：
- 从数组中随机采样
n个元素对； - 计算这些对之间的最小差值 δ；
- 将所有元素按 δ 为单位划分为多个区间；
- 遍历每个区间及其相邻区间，找出最小差值对。
✅ 这种方法的关键在于：最小差值对一定在同一个区间或相邻区间中。
4.2 伪代码实现
algorithm RabinsAlgorithm(a):
// INPUT
// a = an array of n numbers
// OUTPUT
// (p, q) = a pair with the minimal absolute difference in a
S <- sample n pairs of elements (a[i], a[j]) (i != j)
δ <- compute the minimal difference between the numbers in the same pairs in S
(p, q) <- the closest pair in S
segments <- make an empty dictionary
for i <- 1 to n:
k <- floor(a_i / δ)
Insert a[i] into segments[k]
for k in sort(segments.keys):
(x_k, z_k) <- find the closest pair in segments[k]
(p, q) <- the closer between (p, q) and (x_k, z_k)
if k > 1 and segments[k-1] exists:
Find the closest pair of points (x_k, z_{k-1}) such that
x_k is in segments[k] and
z_{k-1] is in segments[k-1]
(p, q) <- the closer between (p, q) and (x_k, z_{k-1})
return (p, q)
4.3 时间复杂度分析
- 随机采样：
O(n) - 划分区间：
O(n) - 遍历每个区间及其相邻区间：
O(n)
因此，整个算法的**期望时间复杂度是线性的 O(n)**，且有很高的概率达到这个性能。
5. 小结
我们介绍了两种在数组中寻找最小差值元素对的方法：
| 方法 | 时间复杂度 | 特点 |
|---|---|---|
| 排序法 | O(n log n) |
简单、稳定，适合大多数情况 |
| Rabin 随机算法 | O(n)（期望） |
更快，适合大规模数据，但实现稍复杂 |
✅ 如果你追求极致性能，Rabin 算法是一个不错的选择；
✅ 如果你追求实现简单和稳定性，排序法更合适。
两种方法各有千秋，根据实际场景选择即可。