私はJavaで次の問題を解決しようとしています(他のほとんどの言語でも実行できますが):
x軸上のdataPointを表す整数値との2つの配列が与えられますxs
。ys
それらの長さは同じではない可能性がありますが、両方とも> 0であり、ソートする必要はありません。計算したいのは、ポイントの2つのデータセット間の最小距離測度です。つまり、たとえば、それぞれについて、セット内でx
最も近いものを見つけて距離を計算します。例えば:y
ys
(x-y)^2
xs = [1,5]
ys = [10,4,2]
(1-2)^ 2 +(5-4)^ 2 +(5-10)^2を返す必要があります
距離測度は重要ではありません。これは私が興味を持っているアルゴリズムです。ブルートフォースよりも優れたものを実現するために、両方の配列を並べ替えて、これらの配列の両方でインデックスを進めることを考えていました(xの各要素について、ysのすべての要素をスキャンして見つけます) min)これはO(len1 * len2)
。
これは私が取り組んでいる私自身の問題であり、宿題の質問ではありません。すべてのヒントをいただければ幸いです。