1000たとえば、最大要素を含むことができる配列があります。それが生み出すことができる数の範囲は言う1 to 10^10です。minimal absolute difference次に、配列内の2つの数値の間を見つける必要があります。私は2つのアルゴリズムを考えました：
最初のものについてはbinarysearch、ソートされた配列内の挿入される数値の位置を見つける関数を定義しました。次に、指定された配列の最初の番号のみでソートされた配列を開始し、2番目の要素以降で指定された配列の反復を開始します。番号ごとに、並べ替えられた配列でその位置を見つけます。その位置の数値がこの数値である場合、差は0であり、可能な限り最小の数値であるため、ループを終了します。それ以外の場合は、その時点で並べ替えられた配列に番号を挿入し、その番号とその配列の前後の番号の違いを確認します。次に、この結果と前の結果の最小値を保存し、この方法で続行します。
2番目：クイックソートを使用して配列をソートします。（範囲が広すぎるので、基数ソートはそれほど効率的ではないと思います）。次に、それを繰り返し、2つの連続する数値が等しい場合は、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";