algorithm - 查找数组中两个数字之间的最小绝对差的最佳算法

Question

有一个数组最多可以包含1000 个元素。它可以产生的数字范围是 1 到 10^10。现在我必须找到数组中两个数字之间的最小绝对差。我想到了两种算法:

对于第一个，我定义了一个binarysearch 函数，它在排序的数组中查找要插入的数字的位置。现在我只使用给定数组的第一个数字开始排序数组，并从第二个元素开始迭代给定数组。对于每个数字，我找到它在排序数组中的位置。如果那个位置的数就是这个数，那么差就是0，就是最小的那个，所以退出循环。否则，我会在此时将数字插入已排序的数组，然后检查该数字与该数组中的前一个和下一个数字之间的差异。然后我存储这个结果和之前结果的最小值，并以这种方式继续。

第二:我使用快速排序对数组进行排序。 (范围太大，所以我认为基数排序不会那么有效)。然后我对其进行迭代，如果两个连续数字相等，则以 0 的答案突破，否则存储该数字与前一个数字和前一个结果之间的差异的最小值。

哪个会更有效率？

有没有更好的算法？

Stackoverflow 在这方面有很多帖子，但它们并没有太大帮助。这是我在 Perl 中的代码:

sub position {
    my @list   = @{$_[0]};
    my $target = $_[1];

    my ($low,$high) = (0, (scalar @list)-1);

    while ($low <= $high) {
        $mid = int(($high + $low)/2);

        if ( $list[$mid] == $target ) {

            return $mid;
        }
        elsif ( $target < $list[$mid] ) {

            $high = $mid - 1; 
        }
        else {

            $low = $mid + 1;
        }
    }
    $low;
}
sub max { $_[0] > $_[1] ? $_[0] : $_[1]; }
sub min { $_[0] > $_[1] ? $_[1] : $_[0]; }

$ans        = 10_000_000_000;
@numbers    = (234, 56, 1, 34...123); #given array
($max,$min) = @num[0, 0];
@sorted     = ($numbers[0]);

for ( @num[1 .. $#num] ) {
    $pos = position(\@sorted, $_);

    if ( $sorted[$pos] == $_ ) { 

        $ans = 0;
        last;
    }
    splice @sorted, $pos, 0, $_;

    if ( $#sorted == $pos ) { 

        $ans = min($_-$sorted[-2], $ans);
    }
    elsif ( 0 == $pos ) {

        $ans = min($sorted[1]-$_, $ans);
    }
    else { 

        $ans = min(min(abs($sorted[$pos-1]-$_), abs($sorted[$pos+1]-$_)), $ans);
    }
    $max = max($_, $max);
    $min = min($_, $min);
}
print "$ans\n";

Answer 1

您最多有 5k 个元素。

请注意 sandy bridge处理器有 32KB L1-Cache ，假设 4 字节整数 - 这意味着它可以包含 8192 个整数。

我会尽量避免创建额外的数据(计数器等除外)，并使用同一个数组就地完成所有操作。这将使 cache-misses 的数量成为非常小，可能会胜过任何算法。

因此，对数组中的元素进行就地快速排序和迭代可能会比任何其他解决方案都好，既可以提高缓存效率，又可以保持适当的渐近复杂度 O(nlogn)。

注意 - 虽然此解决方案可能更有效(至少理论上如此)，但规模仍然很小 - 除非你要多次执行此操作 - 它只是没有不值得花时间对其进行过度优化。

---

一般提示:在讨论小规模问题(最多 5000 个元素符合此标准)时，大 O 表示法通常是不够的。缓存性能通常是这些问题的主导因素。