重複をその場で削除する
遅いポインターと速いポインターの組を使います
「重複をその場で削除する」はCoddyKit上の無料Competitive Programming Academyレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCompetitive Programming Academy学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Competitive Programming Academyコースには全4レッスンが含まれています。
重複をインプレースで削除する
ソート済み配列が与えられたとき、追加の配列を使わずに各値を1つずつ残します。インプレースで処理すればメモリを節約でき、面接でもよく問われる典型問題です。🧹
ソート済みだと有利な理由
配列がソート済みなら、すべての重複は同じ値のすぐ隣に並びます。そのため、配列全体ではなく隣り合う要素だけを比較すれば済みます。
2つの役割、2つのポインタ
最後に保持した値を示す slow ポインタと、前方を走査して新しい値を探す fast ポインタを使います。
slow = 0
fast = 1slow ポインタが書き込む
slow は書き込み位置だと考えてください。slow 以前の要素は、すでに整理されて重複がない状態です。
fast ポインタが読み取る
fast ポインタは前方を読み取るだけです。先へ進み、まだ保持していない値を見つけたときだけ slow に知らせます。
繰り返しを飛ばす
a[fast] が a[slow] と等しければ、それは重複なので、何もせず fast だけを進めます。重複した値は静かに通り過ぎます。
for fast in range(1, n):
if a[fast] == a[slow]:
continue新しい値を見つける
a[fast] が異なる場合は、slow を進めて、そこへ新しい値をコピーします。これにより、古い重複データが新しい重複のないデータで上書きされます。
else:
slow += 1
a[slow] = a[fast]答えは長さになる
走査後の slow + 1 が、配列の先頭に詰められた重複のない値の個数になります。
return slow + 1末尾は無視する
重複のない先頭部分の後ろにある要素は、残った不要なデータです。問題で必要なのは最初の slow + 1 個だけなので、末尾はそのままにします。
空の配列に注意する
空の配列に重複のない値は0個です。開始前に n == 0 を確認し、配列の末尾を越えて読み取らないようにしてください。
if n == 0:
return 01回の走査、追加領域なし
この slow-fast パターンは、時間計算量 O(n)、追加領域 O(1) で動作します。これは、メモリ制限が厳しい場合にまさに求められる方法です。
確認問題
ソート済み配列で、slow と fast のポインタを使ってインプレースに重複を削除しています。
まとめ
ソート済み配列では、slow-fast の組で追加領域を使わずに O(n) の1回の走査で重複を削除できます。重複のない値の個数は slow + 1 です。🎉
よくある質問
「重複をその場で削除する」レッスンは無料ですか？
はい。「重複をその場で削除する」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Competitive Programming Academyコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Competitive Programming Academyコースには全4レッスンが含まれています。
「重複をその場で削除する」で何を学びますか？
遅いポインターと速いポインターの組を使います ブラウザで直接実行するハンズオンコードでCompetitive Programming Academyを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
Competitive Programming Academyを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのCompetitive Programming Academyは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。
「重複をその場で削除する」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このCompetitive Programming Academyレッスンでコードを書いて実行できますか？
はい。すべてのCompetitive Programming Academyレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。