アルゴリズムについて

Question

昇順に並べられている配列aとbがあったときにiとjはそれぞれの配列の要素を指定する。|a{i}-b{j}|の最小値を求める
オーダー(m+n)を満たす（mは配列aの長さnはbの長さ）アルゴリズムがどのような名称のものがあるのか教えて頂きたいです
よろしくお願いいたします

Comments

[y_waiwai]

m と n ってのはなんでしょうか。意味不明になってますよ

[BeatStar]

定義が曖昧です。

i と j はなんでしょうか。i = j とするのか、『aとbのそれぞれの要素の和』という感じでランダムな意味なのか。

O(m+n) とありますが、m と n がそれぞれ定義されていません。

[linkinpark]

すいません修正しました！
よろしくお願いします

[m.ts10806]

タイトルに要件がないので、具体的に。現状は質問タグと同じ単語を繰り返してるだけです。

Answer 1

貪欲法かな。
貪欲法は簡単に言えば「その時点での最適解を選択し続ける」方法です。

例えば、下記のアルゴリズムで探索するとΟ(m+n)。

1. i = 0; j = 0; ans = +INF から開始
2. |a[i] - b[j]| と ans のうち小さい方を新しいansとする。
3. a[i]、b[j]のうち、値の小さい方の添え字を+1する。
4. i > m , j > n, ans == 0 のいずれかが満たされれば探索終了
5. そうでなければ2に戻る

Comments

[linkinpark]

ありがとうございました！
また機会がありましたらよろしくお願いします！！