比较数组中的100万个整数而不先对其进行排序

Question

我有一个任务是找到随机数组中每个整数之间的差异,并返回最低的差异.要求是整数可以在0和int.maxvalue之间,并且数组将包含100万个整数.

我把一些代码放在一起,对于少量的整数工作正常,但是花费很长时间(我大部分时间都放弃等待)要做一百万.我的代码如下,但我正在寻找有关如何提高性能的一些见解.

for(int i = 0; i < _RandomIntegerArray.Count(); i++) {
  for(int ii = i + 1; ii < _RandomIntegerArray.Count(); ii++) {
    if (_RandomIntegerArray[i] == _RandomIntegerArray[ii]) continue;

    int currentDiff = Math.Abs(_RandomIntegerArray[i] - _RandomIntegerArray[ii]);

    if (currentDiff < lowestDiff) {
      Pairs.Clear();
    }

    if (currentDiff <= lowestDiff) {
      Pairs.Add(new NumberPair(_RandomIntegerArray[i], _RandomIntegerArray[ii]));
      lowestDiff = currentDiff;
    }
  }
}

向每个指出我不排序的人道歉; 不幸的是,不允许排序.

Answer 1

想象一下,你已经找到一对整数a,并b从随机阵列,使得a > b和a-b是对所有可能的阵列中的整数中最低的.

确实的整数c数组中的存在,使得a > c > b,即c间推移a和b？很明显,答案是"不",因为否则你会选择这对{a, c}或者{c, b}.

这给出了您的问题的答案:a并且b必须在排序的数组中彼此相邻.排序可以在O(N*log N)中完成,搜索可以在O(N)中完成 - 这是对O(N ²)算法的改进.