问在整数数组中找到使abs(v[i]-v[j])最小化的元素对

EN

对列表进行排序并减去最近的两个元素

证明了最优解是渐近线性O(n) up，直到因子不变。

这意味着所花费的时间与数组中元素的数量成正比(这当然是我们所能做的最好的事情，因为我们至少必须读取数组中的每个元素，这已经花费了O(n)时间)。

这里有一个这样的O(n)解决方案(如果列表可以就地修改，它也使用O(1)空间)：

int mindiff(const vector<int>& v)
{
    IntRadixSort(v.begin(), v.end());

    int best = MAX_INT;

    for (int i = 0; i < v.size()-1; i++)
    {
        int diff = abs(v[i]-v[i+1]);
        if (diff < best)
           best = diff;
    }

    return best;
}

IntRadixSort是一个线性时间固定宽度整数排序算法，定义如下：

http://en.wikipedia.org/wiki/Radix_sort

其概念是，通过在位位置上将整数划分为一系列固定的遍，来利用它们的固定位宽特性。即在hi位(32位)上划分它们，然后在下一个最高位(31位)上划分它们，然后在下一个位(30位)上划分它们，依此类推-这只需要线性时间。

这个问题等同于排序。可以使用任何排序算法，最后返回最近元素之间的差值。可以使用对数据的最终传递来找出差异，也可以在排序过程中对其进行维护。在对数据进行排序之前，相邻元素之间的最小差异将是一个上限。

因此，要在没有两个循环的情况下执行此操作，请使用没有两个循环的排序算法。在某种程度上，它感觉像是语义，但递归排序算法只需一次循环。如果这个问题是简单的双循环情况所需的n(n+1)/2减法，则可以使用O(n+1)算法。