Рубрики
Без рубрики

Проблема ежедневного кодирования Java #004

Daily Coding Problem – это веб-сайт, который каждый день будет отправлять вам на ваш почтовый ящик задачу по программированию… Помечено как java, вызов, новички, ежедневная проблема с кодированием.

Daily Coding Problem – это веб-сайт, который каждый день будет отправлять вам на ваш почтовый ящик задачу по программированию. Я хочу показать новичкам, как решить некоторые из этих проблем с помощью Java, так что это будет продолжающаяся серия моих решений. Не стесняйтесь выбирать их отдельно в комментариях!

Проблема

Учитывая массив целых чисел, найдите первое недостающее положительное целое число в линейном времени и постоянном пространстве. Другими словами, найдите наименьшее положительное целое число, которого не существует в массиве. Массив также может содержать дубликаты и отрицательные числа.

Например, ввод [3, 4, -1, 1] должен дать 2 . Входной сигнал [1, 2, 0] должно дать 3 .

Вы можете изменить входной массив на месте.

Стратегия

Спойлеры! Не смотрите ниже, если не хотите увидеть мое решение!

То, как я интерпретирую эту проблему, заключается в том, что мы ищем наименьшее целое значение, большее 0, которое не отображается в массиве. Таким образом, если массив содержит 1, 2 и 3, но не 4, код должен возвращать 4 . Дубликаты и отрицательные числа можно игнорировать. Максимальное значение, которое должно быть возвращено, – это длина массива плюс единица, как показано во втором примере, поэтому решение всегда будет находиться между 1 и N+1 включительно, где N – это длина заданного массива.

Моя первая мысль – создать новый массив длины N , заполните его false s и переверните эти false s в true если индекс существует в данном массиве. Но это решение не является решением с постоянным пространством, поскольку для него требуется массив длины N . (Хотя это линейно по времени, так как нам нужно пройти через исходный массив только один раз.) Что мы можем сделать вместо этого?

Массивы примеров не отсортированы, поэтому мы не можем делать никаких предположений о том, что они будут в целом. Исследуя алгоритм сортировки в постоянном пространстве и линейном времени, я нашел this SO answer , который предписывает следующий алгоритм, соответствующий этим требованиям:

  1. Начните с первого элемента массива.
  2. Если индекс его массива соответствует его значению, переходите к следующему.
  3. Если нет, замените его значением в индексе массива, соответствующем его значению.
  4. Повторяйте шаг 3 до тех пор, пока больше не будет необходимости в замене.
  5. Если не в конце массива, перейдите к следующему элементу массива, в противном случае перейдите к шагу 7
  6. Перейдите к шагу 2.
  7. Сделано

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

Это сложная проблема!

В подсказке говорится, что мы можем изменить входной массив на месте, что – на мой взгляд – кажется единственным способом сохранить этот алгоритм как постоянную сложность пространства. (Помимо создания массива true /| false , как описано выше, с длиной, равной Integer. MAX_VALUE .) Поэтому я думаю, что нам нужно сделать что-то похожее на описанное выше, но не совсем то же самое.

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

  1. Перейти к следующему элементу массива (или начать с начала массива, если этот шаг встречается впервые):
  2. Если это последний элемент массива, перейдите к шагу 5.
  3. Если индекс массива этого элемента соответствует его значению, или если его значение равно нулю или отрицательно, вернитесь к шагу 1. В противном случае перейдите к шагу 4.
  4. Поменяйте значение этого элемента на значение, содержащееся в индексе, представленном значением этого элемента, и вернитесь к шагу 3.
  5. Пройдитесь по массиву еще раз, с самого начала, и сравните индексы массива (основанные на 1) со значениями, которые они содержат. Если индекс и значение не совпадают, этот индекс является наименьшим целочисленным положительным значением, которое не содержится в массиве.

Для примера массива, приведенного в приглашении, этот процесс выглядит следующим образом (все индексы на основе 1):

[ 3,  4, -1,  1] -- original array
[-1,  4,  3,  1] -- after swapping 1st and 3rd elements
[-1,  1,  3,  4] -- after swapping 2nd and 4th elements
[ 1, -1,  3,  4] -- after swapping 2nd and 1st elements

Затем мы можем просто обойти массив во второй раз, чтобы найти первый элемент, значение которого не соответствует его индексу. Для двукратного обхода массива требуется N + N времени, или 2N (он же. линейное) время. Поскольку мы модифицируем массив на месте, это также решение с постоянным пространством. Давайте рассмотрим другой пример:

[ -1, -1,  8,  1,  2,  2]

Алгоритм должен возвращать 3 для этого массива. Но когда мы доберемся до третьего элемента ( 8 ), у нас есть проблема: массив содержит менее 8 элементов. Нам нужно добавить еще одно условие к шагу 3 нашего алгоритма:

Если индекс массива этого элемента соответствует его значению, или если его значение равно нулю, отрицательно или больше длины массива, вернитесь к шагу 1. В противном случае перейдите к шагу 4.

Пошаговое выполнение этого второго примера:

[ -1, -1,  8,  1,  2,  2] -- original array
[  1, -1,  8, -1,  2,  2] -- after swapping 4th and 1st elements
[  1,  2,  8, -1, -1,  2] -- after swapping 5th and 2nd elements
[  1,  2,  8, -1, -1,  2] -- ...

И здесь мы сталкиваемся с другой проблемой – дубликатами. У нас будет бесконечный цикл, если мы продолжим пытаться поменять местами 6-й и 2-й элементы в приведенном выше примере. Поэтому мы должны проверить, совпадают ли значения “target” и “source”, и если это так, перейти к следующему элементу массива:

Поменяйте значение этого элемента на значение, содержащееся в индексе, представленном значением этого элемента, если только эти два значения не совпадают, и в этом случае вернитесь к шагу 1.

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

  1. Перейти к следующему элементу массива (или начать с начала массива, если этот шаг встречается впервые):
  2. Если это последний элемент массива, перейдите к шагу 5.
  3. Если индекс массива этого элемента соответствует его значению, или если его значение равно нулю, отрицательно или больше длины массива, вернитесь к шагу 1. В противном случае перейдите к шагу 4.
  4. Поменяйте значение этого элемента на значение, содержащееся в индексе, представленном значением этого элемента, если только эти два значения не совпадают, и в этом случае вернитесь к шагу 1.
  5. Пройдитесь по массиву еще раз, с самого начала, и сравните индексы массива (основанные на 1) со значениями, которые они содержат. Если индекс и значение не совпадают, этот индекс является наименьшим целочисленным положительным значением, которое не содержится в массиве.

… Я думаю, это должно сработать. Давайте попробуем его закодировать!

Код

Итак, первое, что я делаю, – это создаю класс оболочки. Нам понадобится метод, который находит первое отсутствующее целое число и, возможно, main , который запускает два примера в командной строке:

public class DCP004 {

  public static void main (String[] args) {
    findSmallestMissing(new int[]{  3,  4, -1,  1 });
    findSmallestMissing(new int[]{  1,  2,  0 });
  }

  public static int findSmallestMissing (int[] array) {
    // to be implemented
    return -1;
  }

}

Теперь, в find Наименьшее недостающее() , мы захотим реализовать наш алгоритм, описанный выше. Во-первых, давайте настроим цикл для перемещения по массиву:

  public static int findSmallestMissing (int[] array) {

    // if array is null or empty, 1 is the smallest missing number
    if (array == null || array.length < 1) return 1;

    // get the length of the array
    int len = array.length;

    // assume 1 is smallest missing number until proven otherwise
    int smallestMissing = 1;

    // loop over input array (steps 1 and 5)
    for (int ii = 0; ii < len; ++ii) {
      // implement steps 2-4 in here
    }

    // to be implemented
    return -1;
  }

Внутри этого цикла происходит большая часть работы этого алгоритма:

    // loop over input array (steps 1 and 5)
    for (int ii = 0; ii < len; ++ii) {

      // step 3 (make sure to use 1-based indexing)
      if (array[ii] == (ii+1) || array[ii] < 1 || array[ii] > len)
        continue;

      // step 4
      while (array[ii] != ii) {

        // index of the element to swap with
        int swap = array[ii]-1;

        // value of the element to swap with
        int temp = array[swap];

        // swap the values
        array[swap] = array[ii];
        array[ii] = temp;

        // if the new value is < 1 or > len, move to next one
        if (temp < 1 || temp > len) break;
      }
    }

Поскольку мы изменили array на месте, последнее, что нам нужно сделать, это перебрать его и найти первый элемент, значение которого не соответствует его индексу (base-1):

    // loop over modified array
    for (int ii = 0; ii < len; ++ii) {
      if (array[ii] != ii+1) return ii+1;
    }

    return len+1;

Я написал этот код в своем редакторе markdown, не тестируя его, так что давайте вставим все это вместе и посмотрим, работает ли это!

Отладка

jshell> /open DCP004.java

jshell> DCP004.main(new String[]{})

jshell> DCP004.findSmallestMissing(new int[]{1, 2, 0})
$3 ==> 3

jshell> DCP004.findSmallestMissing(new int[]{3, 4, -1, 1})
$4 ==> 1

… хорошо, итак, у нас есть несколько небольших проблем. Во-первых, в main ничего не печатается. Давайте добавим операторы System.out.println вокруг этих вызовов функций в |/main :

  public static void main (String[] args) {
    System.out.println(findSmallestMissing(new int[]{  3,  4, -1,  1 }));
    System.out.println(findSmallestMissing(new int[]{  1,  2,  0 }));
  }

Далее, похоже, что первый массив возвращает правильный результат ( 3 ), но у нас есть проблема со вторым массивом. Он возвращается 1 когда он должен вернуться 2 . Это просто случайная ошибка? Давайте попробуем другой массив:

jshell> DCP004.findSmallestMissing(new int[]{2, 4, -1, 1})
$7 ==> 

… это не имеет возвращаемого значения, потому что мне пришлось его убить – я думаю, что был бесконечный цикл! По крайней мере, я нашел одну проблему. Следующая строка:

      while (array[ii] != ii) {

…вместо этого должно быть

      while (array[ii] != (ii+1)) {

Похоже, это устранило проблему!

jshell> DCP004.findSmallestMissing(new int[]{2, 4, -1, 1})
$9 ==> 3

jshell> DCP004.findSmallestMissing(new int[]{3, 4, -1, 1})
$10 ==> 2

Однако есть еще одна проблема. Этот массив также дает бесконечный цикл:

jshell> DCP004.findSmallestMissing(new int[]{1, 1, 2, 2, 3, 5})
$11 ==> 

…что мы пропустили на этот раз? Для отладки давайте распечатаем массив перед каждой заменой в цикле while :

      // step 4
      while (array[ii] != (ii+1)) {

        // DEBUG: print array
        System.out.println(Arrays.toString(array));

        // index of the element to swap with
        int swap = array[ii]-1;

Выходные данные для последнего примера выглядят следующим образом:

[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
...

Похоже, что ничего никогда не менялось местами! (Или, два 1 буквы s в начале меняются местами снова и снова.) Похоже, мы забыли выйти из while , когда два поменявшихся местами значения идентичны. Давайте добавим к этому подвох:

        // if the new value is < 1 or > len, move to next one
        if (temp < 1 || temp > len) break;

        // if new value equals old value, move to next one
        if (temp == array[ii]) break;

…устранило ли это проблему?

jshell> DCP004.findSmallestMissing(new int[]{1, 1, 2, 2, 3, 5})
[1, 1, 2, 2, 3, 5]
[1, 1, 2, 2, 3, 5]
[1, 2, 1, 2, 3, 5]
[1, 2, 1, 2, 3, 5]
[1, 2, 3, 2, 1, 5]
$15 ==> 4

jshell> DCP004.findSmallestMissing(new int[]{-1, -1, 8, 1, 2, 4})
[-1, -1, 8, 1, 2, 4]
[1, -1, 8, -1, 2, 4]
[1, 2, 8, -1, -1, 4]
$16 ==> 3

…это выглядит так!

Обсуждение

Вот так! Решение в постоянном времени и линейном пространстве, которое также печатает измененный массив перед каждой заменой в диагностических целях. Он отлично работает с примерами массивов и несколькими дополнительными массивами, которые я бросил в него.

Эта проблема потребовала некоторого размышления, чтобы придерживаться ограничений, но это было весело! Кто-нибудь может найти какие-нибудь массивы, которые нарушают мой код?

Весь код для решения моих ежедневных проблем с кодированием доступен по адресу github.com/awwsmm/daily .

Предложения? Дайте мне знать в комментариях.

Оригинал: “https://dev.to/awwsmm/java-daily-coding-problem-004-2ogb”