我得到一个不一定已排序的整数数组。我必须找到一对数字，与数组中的任何其他数字对相比，彼此之间的差异最小。时间效率应该是O(n)。
我很确定你无法获得解决这个问题的通用线性时间算法！
但是，由于您有（有界）整数，因此您可以稍微作弊并从使用基数排序对数组进行排序开始，这是线性时间！然后找到最接近的相邻对，这又是线性的。
如果您正在寻找任何一对不同整数之间的最小绝对差，那么 ltjax 的算法将在线性时间内给您答案。然而，正如问题所述，负数是有效的；在这种情况下，使用线性搜索找到最大的数字 L 和最小的数字 S，那么答案就是 S - L。
我认为如果我通过线性搜索获得第一个最小元素，然后再次应用循环来获得第二个最小元素，这可能不会错。例如 min1=A[0]; for(i=0;iA[i]) min1=A[i]; } min2=A[1]; for(i=1;iA[i]) min2=A[i]; } 差异=min2-min1;
我认为你可以通过这种方式找到最少两个数字并找出差异。 索引 i 指向 0，索引 j 指向 1， 尝试通过 i 在偶数索引中找到 min1，在单次迭代中通过 j 在奇数索引中找到 min2，并子 min1,min2。
如果您知道最大位数，则在空间和时间中应用基数排序 O(n)
这可以在预期的线性时间内完成。请参阅https://cs.stackexchange.com/q/167448/755。
它不太可能在确定的线性时间内完成。请参阅https://cs.stackexchange.com/q/24115/755。