重複を除く併合の空欄

L=[1,3,3,8],R=[2,3,7]は昇順。添字1始まり。番兵L[5]=∞,R[4]=∞を用意し、i=j=1、出力Oは空とする。 while i≤4 OR j≤3 if L[i] < R[j] x ← L[i]; i ← i+1 elseif L[i] > R[j] x ← R[j]; j ← j+1 else x ← L[i]; i ← i+1; j ← j+1 endif if 【条件】 Oの末尾へxを追加 endif endwhile Oを[1,2,3,7,8]とする条件はどれか。ORは左が真なら右を評価しない。

答え・解き方を読む

Oが空 OR Oの末尾≠x

図で見る

二つの昇順列の先頭を比較する

図を拡大して見る ↗

両列の現在位置を比べ、出力した側の位置を進めます。等値を一つにする問題では両位置を進める等、設問の重複処理条件を別に確認します。

図は問題の関係を整理する模式図です。記号には各問題の数値を当てはめます。寸法・面積・時間の縮尺や、実施工の全条件は表していません。

考える順序

1. 1両配列で同値のときは両方を進める
2. 2片方の内部にも重複3があるため出力直前に比較
3. 3空なら追加し、以後は末尾と違う値だけ追加する

選択肢ごとの理由

• 比較 · i≠j

  走査位置の大小は出力値の重複条件ではありません。

• 正解 · Oが空 OR Oの末尾≠x

  両配列で同値のときは両方を進める。片方の内部にも重複3があるため出力直前に比較。空なら追加し、以後は末尾と違う値だけ追加する。

• 比較 · Oが空 OR Oの末尾=x

  等しい場合に追加すると重複が残ります。

• 比較 · Oが空 AND Oの末尾≠x

  空でないと追加できず、空の末尾参照も問題になります。