找到数组中两个数字之间的最小绝对差值的最佳算法

Question

有一个数组,可以包含,例如,最多1000元素.它可以产生的数字范围1 to 10^10.现在我必须minimal absolute difference在数组中找到两个数字之间的数字.我想到了两种算法:

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

第二:我使用quicksort对数组进行排序.(范围太大,所以我认为基数排序不会那么高效).然后我迭代它,如果两个连续的数字相等则以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元素.

请注意,沙桥处理器具有32KB L1-Cache,假设4个字节为整数 - 这意味着它可以包含8192个整数.

我尽量避免创建额外的数据(除了计数器等),并使用相同的数组做所有事情.这将使缓存未命中的数量非常小,并且可能会超过任何算法.

因此,就地快速排序而不是遍历数组中的元素可能会比任何其他解决方案更好,既可以提高缓存效率,又可以保持体面的渐近复杂性O(nlogn).

注意 - 尽管这种解决方案可能效率更高(至少在理论上),但规模仍然很小 - 除非你要多次进行这种操作 - 否则你的时间过度优化并不值得.

一般提示:当谈到小规模问题(并且多达5000个元素符合此标准)时,大O符号通常是不够的.缓存性能通常是这些问题的主要因素.

Answer 2

这是一维中最接近的配对问题.请注意,解决此问题至少与解决元素唯一性问题一样困难,因为如果存在任何重复元素,则答案为0.

元素唯一性问题需要O(n lg n)时间来解决,所以这个问题也必须至少那么难.由于您提出的迭代排序解决方案是O(n lg n),没有更好的渐近最坏情况算法可用.

然而,如维基文章中所述,有些算法的最坏情况运行时间更差,但线性预期运行时间更短.本文描述了一种这样的方法,看起来相当复杂!

Answer 3

第二个问题会更快,原因很简单,第一个解决方案是你在Perl-space中使用自己编写的那种,而第二个解决方案你有机会使用Perl内置的,sort这是一个C功能非常快.如此小的投入,即使它有可能减少工作,第一个获胜也几乎是不可能的.