JavaScriptアルゴリズム:popメソッドだけで配列から負の値を削除する

複数の値を持つ配列X(例:[-3, 5, 1, 3, 2, 10])が与えられたとき、配列内の負の値をすべて取り除く関数を作成します。

関数の実行後には、配列が正の数だけで構成されている必要があります。さらに、一時的な配列を新たに作成せず、pop()メソッドのみを使って要素を削除することが求められます。

解決のアプローチ

この問題を解く鍵は「配列の末尾から処理する」ことです。まずwhileループで末尾に連なる負の値をすべてpop()で除去し、その後、配列を後ろから前へ向かって走査します。走査中に負の値を見つけたら、その位置へ配列の最後の要素(正であることが保証されています)を代入してからpop()すれば、一時配列なしで元の配列内だけで処理を完結できます。

1. ステップ1: whileループで、配列の末尾が負である限りpop()を繰り返します。
2. ステップ2: forループでインデックスを末尾から先頭へ逆順に走査します。
3. ステップ3: 負の値を検出したら、その要素を末尾の正の値で上書きし、pop()で削除します。

サンプルコード

以下が実際のコードです。

function removeNegatives(x) {
  // 配列の末尾にある負の値をすべて削除
  while (x.length && x[x.length - 1] < 0) {
    x.pop();
  }
  // 末尾から先頭に向かって走査
  for (var i = x.length - 1; i >= 0; i--) {
    if (x[i] < 0) {
      // この要素を最後の要素(正であることが保証されている)で置き換える
      x[i] = x[x.length - 1];
      x.pop();
    }
  }
}

var x = [-3, 5, 1, 3, 2, 10];
removeNegatives(x);
console.log(x);

実行結果

コンソールには次の出力が表示されます。

[ 5, 1, 3, 2, 10 ]

このアルゴリズムのメリット

• 追加メモリ不要: 新しい配列を生成せず元の配列を直接書き換えるため、メモリ効率に優れています。
• 線形時間 O(n): 各要素を一度だけ確認し、削除は常にO(1)で動作するpop()で行うため高速です。
• 順序が保持される: 後ろから処理するため、残った正の値同士の相対的な並び順は変わりません。