Перемещение нулей

Последний день я думал обо всех возможных способах, которыми я мог найти, чтобы решить следующую проблему:

Учитывая массив случайных целых чисел, переместите все нули в массиве до конца массива.

Сначала это казалось довольно простой проблемой, но в вызове также говорится:

Постарайтесь сохранить это в O (n) время (или лучше)!

В порядке. Все стало более интересным.

Этот вызов пришел из Информационный бюллетень Cassidoo И каждую неделю она публикует новый вопрос интервью. Если вы еще не подписаны на это, я действительно призываю вас сделать это.

Потратив некоторое время на то, чтобы подумать об этом, я наткнулся на несколько способов решения проблемы, переходя от процедурных к функциональным стилям. Я думал, было бы интересно поделиться, так что мы пойдем:

Пузырька

Этот подход основан на алгоритме сортировки пузырьков, и идея состоит в том, чтобы «пузырьть» нули до конца массива.

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;
}

Мы храним переменную LASTCEROINDEX который указывает на последнюю нулевую позицию. Когда мы сталкиваемся с числом, которое не является нулевым, мы обменяем это значение с последней позицией.

Этот алгоритм работает во время 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)];
}

Я явно предвзято, но я нахожу это наиболее читаемым решением из всех из них. Производительность не является ключевым моментом этого подхода, поскольку в процессе он создает много промежуточных массивов. Также рекурсия может быть проблемой с большими массивами (хотя ее можно решить с помощью оптимизации хвостового вызова )

Группировка

Этот подход фильтровал номера в два массива, нули и ненулевые, затем массивы сглаживаются в один, толкая нули вправо:

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

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

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

Сплайс

Еще один, на этот раз, используя сплайс для вставки чисел и нулей в их соответствующем месте. Этот метод частично основан на том, как работает алгоритм сортировки вставки:

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

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

  return output;
}

Сортировать

И последний, используя сортировку. В конце концов, перемещение нулей – это не что иное, как сортировка чисел, верно? Здесь мы используем функцию сравнения, которая при сравнении нуля с другим номером будет поставить ноль после другого номера. В противном случае сохранит первоначальный заказ.

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

Этот внутренне может использовать алгоритм быстрого сортировки, который работает в O (n * log n)

Вывод

Одна из вещей, которые мне больше всего нравится в программировании, – это так много способов решить данную проблему. И с каждым решением мы изучаем новые способы подхода к будущим.

Оригинал: “https://dev.to/edulan/moving-zeros-2g36”