高速道路の同じ車線にあるさまざまな車の位置が、ベクトルの double として順不同で与えられます。O(n) 時間で隣接する車間の最大のギャップを見つけるにはどうすればよいでしょうか?
簡単な解決策はソートしてからチェックすることのようですが、もちろんこれは線形ではありません。
1689 次
2 に答える
7
ベクトルを n+1 個の等しいサイズのバケットに分割します。そのようなバケットごとに、最大値と最小値を保存します。他のすべての値は破棄できます。ピジョンホールの原則により、これらの部分の少なくとも 1 つが空であるため、いずれかの部分の非最小値/非最大値は結果に影響しません。
次に、バケットを調べて、次および前の空でないバケットまでの距離を計算し、最大値を取得します。これが最終結果です。
n=5 で値が 5、2、20、17、3 の例。最小は 2、最大は 20 => バケット サイズは (20-2)/5 = 4 です。
Bucket: 2 6 10 14 18 20
Min/Max: 2-5 - - 17,17 20,20
違い: 2-5、5-17、17-20。最大は 5 ～ 17 です。
于 2013-02-27T20:27:35.300 に答える