2つの配列の最小の差を求める

2つのソートされた配列AとBがあると、| A [i] -B [j] |最小です。2つの配列の最小の差を求める

2010-12-10 dharm0us

あなたが質問として知りたいと思っているフレーズをお願いします。 –

宿題に2つの質問がある場合は、少なくとも自分で試してみる必要があります。 –

彼は、2つの異なる配列内の任意の2つのアイテム間の最小距離を見つける最も効率的な方法を知りたいと考えています。 – sethvargo

配列はソートされているので、2つのポインタ（各配列に1つ）を渡すことができます。 |A[i+1] - B[j]| < |A[i] - B[j+1]|の場合は、iをインクリメントし、それ以外の場合はjをインクリメントします。いずれかの配列の終わりに達するまで続行します。最小限のインデックスを追跡してください。

出典

2010-12-10 18:48:13 marcog

このコードの最悪の実行時間の複雑さは何ですか？それはn^2でなければなりませんか？ – Yashasvi

O（nlogm）： Aの各要素について、Binary Searchメソッドを使用して、配列Bに最も近い値を持つ要素を見つけます。 – Yashasvi

このような答えを自分自身で見つけ出すにはどうすればよいですか？あなたがそれを解決するために使った方法は何でしたか？ –

2つの配列の最小の差を求める

答えて

関連する問題