ソート済みリストの重複削除
同じ値が続けて並んでいる列から、重複を 1 つにまとめます。すでに並べ替えてあるなら、同じ値は必ず隣どうしにいます。この前提が効いてきます。
set に入れると、並び順が消える
重複を消すだけなら、集合に入れて取り出すのが早そうに見えます。ところが集合は中身の順序を約束しません。せっかく並べ替えてあった情報が、そこで捨てられます。時刻順のログや、順位のついた一覧では使えない手です。
言語によっては、たまたま入れた順で出てくることもあります。それがいちばん厄介です。手元では通り、本番で並びが崩れます。順序に意味があるなら、順序を保証する書き方を選んでください。
並んでいるという前提を活かせば、集合はそもそも要りません。同じ値が離れて現れることは無いので、隣とだけ比べれば足ります。
隣が同じなら、鎖から外す
札でつないだリストなら、新しい入れ物を作らずにその場で外せます。自分の次が自分と同じ値なら、その次のさらに次へ札を張り替えます。
Python
cur = head
while cur is not None and cur.next is not None:
if cur.value == cur.next.value:
cur.next = cur.next.next # 1 つ飛ばす
else:
cur = cur.nextJavaScript
let cur = head;
while (cur !== null && cur.next !== null) {
if (cur.value === cur.next.value) {
cur.next = cur.next.next;
} else {
cur = cur.next;
}
}外されたノードは、どこからも指されなくなって消えます。書き換えたのは札 1 枚だけで、他のノードは 1 つも動いていません。
外したときは、進まない
上のコードで、飛ばした側に cur = cur.next が無いのは書き忘れではありません。1, 1, 1 のように 3 つ続く場合を考えてください。
1 つ飛ばした直後、cur はまだ 1 つ目の 1 にいて、その次が 3 つ目の 1 になっています。ここで進んでしまうと、3 つ目が生き残ります。飛ばしたときは同じ場所に留まってもう一度隣を見る、違う値に出会ったときだけ進む。この使い分けが要です。
条件を cur.next まで確かめているのも同じ理由です。次が無い場所で cur.next.value を読むと落ちます。末尾の 1 つ手前で止まる書き方になっているか、確かめてください。
実務で出てくるのは、時系列に並べたイベントから、同じ状態が続く区間を 1 件にまとめる場面です。センサーの値でも画面の操作履歴でも、変化した瞬間だけ残したいことが多い。並んでいるなら、隣を見るだけで切れ目が分かります。
新しい列に詰め直す書き方もあります。どちらで書くにせよ、1, 1, 1 と 1, 2, 3 の 2 つで試すと、進める判断を間違えていないかがすぐ分かります。
要件
- 入力は昇順ソート済みの配列であると仮定して良い
- 連続する重複を除去し、順序を保った配列を返す
- set() などで順序を崩さず、1 パスで処理すること
入出力例
removeDuplicates([1,1,2,3,3]) → [1,2,3]
removeDuplicates([1,1,1]) → [1]
removeDuplicates([1,2,3]) → [1,2,3]
removeDuplicates([1]) → [1]
removeDuplicates([1,1,2,2,3,3,4,4]) → [1,2,3,4]ヒント
