移動ゼロ

移動ゼロ
最後の日、私はすべての可能な方法について考えていました.
ランダムな整数の配列が与えられた場合、配列内のすべてのゼロを配列の最後まで移動します.
最初はかなり単純な問題のように見えましたが、チャレンジも述べました.
これをo ( n )時間(またはより良い)に保つようにしてください!
よろしい.物事はもっと面白くなった.
この挑戦はcassidoo's newsletterから来ました、そして、毎週、彼女は新しいインタビュー質問を掲示します.あなたがまだそれに加入していないならば、私は本当にあなたがそうするのを奨励します.
それについて考えるいくつかの時間を取った後に、私は問題を解決するいくつかの方法に遭遇しました.私は、それが共有するのがおもしろいと思いました、そこで、ここで、我々は行きます:

バブリング
このアプローチはバブルソートアルゴリズムに基づいており、アイデアは配列の最後までゼロを「バブルアップ」することです.

function moveZeros(input) {
  for (let i = 0, lastZeroIndex = -1; i < input.length; i++) {
    const n = input[i];

    if (n === 0 && lastZeroIndex < 0) {
      lastZeroIndex = i;
      continue;
    }

    if (n !== 0 && lastZeroIndex >= 0) {
      input[lastZeroIndex++] = n;
      input[i] = 0;
    }
  }

  return input;
}

我々は、最後のゼロ位置を指す可変lastZeroIndexを格納します.0以外の数に遭遇すると、その値を最後の位置に置き換えます.
このアルゴリズムはo(n)時間で行い,最も効率的である.これは、手続きのスタイルで書かれ、元の配列を突然変異、パフォーマンスについて話すとき、突然変異は通常最速のオプションです.

再帰
機能的プログラミングの大ファンで、これは私のお気に入りのものです.アイデアは、入力配列を最初と残りの部分に分割することです.最初の項目がゼロの場合、我々は最後にそれを移動し、次のmoveZeros呼び出しに残りの部分を委任する.そうでなければ、我々は現在の位置でそれを維持します.

function moveZeros([first = null, ...rest]) {
  switch (first) {
    case null:
      return [];
    case 0:
      return [...moveZeros(rest), first];
    default:
      return [first, ...moveZeros(rest)];
  }
}

パターンマッチング提案を使用した別のバージョン

const moveZeros = (input) => case (input) {
  when [] -> [];
  when [0, ...rest] -> [...moveZeros(rest), 0];
  when [number, ...rest] -> [number, ...moveZeros(rest)];
}

私は明らかに偏っています、しかし、私はそれがそれらのすべての最も読みやすい解決を見つけます.パフォーマンスはこのアプローチの重要なポイントではありません.また、大きな配列で問題が起こります(tail call optimizationで解決できますが)

グループ化
このアプローチは2つの配列、ゼロと非ゼロの数をフィルタリングします、そして、配列は1に平らにされます.

function moveZeros(input) {
  input
    .reduce(
      (groups, number) => {
        const [nonZeros, zeros] = groups;

        if (number === 0) {
          zeros.push(0);
        } else {
          nonZeros.push(number);
        }

        return groups;
      },
      [[], []]
    )
    .flat();
}

継手
もう1つは、この時間のspliceを使用して番号とゼロの対応する場所に挿入します.このメソッドは、部分的に挿入ソートアルゴリズムがどのように機能するかに基づいています.

function moveZeros(input) {
  let output = [];
  let lastZeroIndex = 0;

  for (const number of input) {
    output.splice(number === 0 ? lastZeroIndex : lastZeroIndex++, 0, number);
  }

  return output;
}

ソート
と最後の1つ、並べ替えを使用します.最後にゼロの移動では、ソート番号よりも何もないですか?ここで、比較関数を使用して、ゼロを他の数値と比較するときに、他の数値の後にゼロを置きます.それ以外の場合は元の順序を保持します.

function moveZeros(input) {
  return input.sort((_, number) => (number === 0 ? -1 : 0));
}

これは内部的に簡単なソートアルゴリズムを使うかもしれません.

結論
プログラミングに関して一番好きなのは、与えられた問題を解決しなければならない多くの方法です.そしてあらゆる解決策で、我々は将来のものに近づく新しい方法を学びます.