由于未排序整数数组，并没有在做任何假设 阵列中的数字： 是否有可能找到两个号码的 差最小的O（n）的时间？

Given an unsorted integer array, and without making any assumptions on the numbers in the array: Is it possible to find two numbers whose difference is minimum in O(n) time?

编辑： A，B被定义为两个数字之间的差异 ABS（AB）

Difference between two numbers a, b is defined as abs(a-b)

推荐答案

在列表中找到最小和最大的元素。差最小的最大将是最小

Find smallest and largest element in the list. The difference smallest-largest will be minimum.

如果你正在寻找非负的差异，那么这当然是至少硬如检查，如果阵列有两个相同的元素。这就是所谓的元唯一性问题并没有任何额外的假设（如限制整数的大小，从而比其他操作比较）要求> = N日志N时间。它是寻找最接近一对点的的一维情况。

If you're looking for nonnegative difference, then this is of course at least as hard as checking if the array has two same elements. This is called element uniqueness problem and without any additional assumptions (like limiting size of integers, allowing other operations than comparison) requires >= n log n time. It is the 1-dimensional case of finding the closest pair of points.