algorithm - 配列 O(n) からすべてのゼロを削除します。余分なメモリはありません

Question

外部メモリなしで O(n) 時間で指定された配列からすべてのゼロを削除するための最良のアルゴリズムを教えてください。たとえば、1 2 0 0 3 2 0 2 は 1 2 3 2 2 になります。

Answer 1

2 つのポインターを使用します。1 つは読み取り用で、もう 1 つは書き込み用です。

• 配列のリーダー ポインターを使用して反復します。要素がゼロの場合は、それのみを増やします。
• 要素がゼロでない場合は、それを書き込んで両方のポインターを増やします。