是否存在O(n+m)线性时间解法求两个数组元素的最小非负差值

分两种场景给出明确结论：

• 若两个数组的元素取值范围是有已知固定上限的非负整数，存在线性时间O(n+m)解法，不需要显式排序
• 若元素是无取值限制的通用整数，在基于比较的计算模型下不存在严格线性时间解法，时间下界为Ω(n log n + m log m)

思路是通过计数标记+前后最近存在数组实现，不需要排序操作：

1. 假设两个数组元素最大值为K，初始化长度为K+1的布尔数组exist，遍历数组A，将所有A中出现过的值对应的exist[v]设为true
2. 预处理两个辅助数组：
   • left[v]：表示小于等于v的数中，最近的在A中出现过的数值
   • right[v]：表示大于等于v的数中，最近的在A中出现过的数值
3. 遍历数组B的每个元素x，计算min(x - left[x], right[x] - x)，记录全局最小值即可

该方法时间复杂度为O(n + m + K)，当K为固定常量时，整体复杂度为线性O(n+m)。

我们可以通过问题归约法证明下界：

基于比较的计算模型下，「元素唯一性问题」（判断一个数组中是否存在重复元素）的时间下界是Ω(n log n)，这是已经被严格证明的经典结论。

我们可以将元素唯一性问题归约到本题的最小差值问题：

1. 假设我们需要判断数组X是否存在重复元素，构造两个数组A = X、B = X
2. 调用本题解法求A和B的最小非负差值，如果差值为0则说明X存在重复元素，否则不存在

如果本题存在O(n+m)的线性解法，那么元素唯一性问题就可以在O(n)时间内解决，和已证明的Ω(n log n)下界矛盾，因此通用场景下不存在严格线性时间解法。

补充：如果允许接受平均线性时间复杂度，也可以用哈希表存储A的所有元素，遍历B的每个元素x时，从x开始逐步向正负方向查询哈希表，直到找到存在的元素计算差值。但该方法最坏时间复杂度会退化到O((n+m)*D)，D为实际最小差值的大小，不属于严格的最坏线性时间解法。

目前通用场景下的工业界最优解法是排序+双指针法，时间复杂度为O(n log n + m log m)，示例运行流程如下：

输入: A = [1, 3, 15, 11, 2], B = [23, 127, 235, 19, 8]
运行步骤：
1. 排序A得到 [1,2,3,11,15]，排序B得到 [8,19,23,127,235]
2. 初始化指针i=0、j=0、最小差值min_diff为无穷大
3. 计算当前差abs(A[i]-B[j])=7，更新min_diff=7，因A[i]更小，i右移到1
4. 重复上述比较逻辑，每次移动指向更小元素的指针，直到其中一个指针遍历完成，最终得到最小差值3

内容的提问来源于stack exchange，提问作者Rabih Sarieddine