Блог

Главная - Вопросы по программированию - Обнаружение цикла Флойда для чисел, имеющих повторение в O(n) времени и O(1) пространстве

Обнаружение цикла Флойда для чисел, имеющих повторение в O(n) времени и O(1) пространстве

#algorithm

Вопрос:

Можно ли изменить алгоритм обнаружения циклов Флойда, чтобы найти все числа, имеющие повторение в массиве? Я не могу изменить массив.

Учитывая массив для размера n с целыми 1,...n-1 числами , по принципу ячейки, существует повторяющееся целое число. — *

Реализация алгоритма обнаружения циклов Флойда успешно помогает найти дубликат во O(n) времени и O(1) пространстве.

Я хочу разобраться со случаем, когда существует более одного дубликата. Это мои мысли:

  1. Каждое повторение числа приводит к циклу (при условии *). Но никакие два разных целых числа, имеющих повторение, не могут находиться в одном и том же цикле. Поэтому мы должны найти все такие циклы.
  2. Каждый путь цикла будет иметь форму --------o , в которой --------- та часть, с которой мы начинаем два указателя для нашего алгоритма определения цикла, o является циклом.
  3. Нам нужно найти точки входа в цикл, поэтому мы держим один указатель на первом - месте в нашем цикле, а другой-там, где указатели встретились изначально, перемещение их вместе с одинаковой скоростью приведет к тому, что они встретятся в точке входа цикла.
  4. Поэтому, если у нас есть первый - из нашего «Циклического пути», мы можем найти дубликат, который привел к этому циклу.

Как мне найти первую - оптимальную для каждого велосипедного пути? Хранение посещенных узлов просто приведет к потере этой сложности пространства O(1), и было бы относительно лучше вместо этого просто использовать хэш-таблицу.

Мне нужно было бы сохранить некоторую информацию, чтобы сообщить, что велосипедный путь уже посещен, поэтому места не может быть O(1) в соответствии с моим пониманием, но как мне в любом случае минимизировать пространство.

Возможен ли вообще такой подход, не ошибаюсь ли я где-то в приведенных выше идеях? Какой другой метод был бы осуществим, используя обнаружение циклов и оптимальное нахождение нескольких дубликатов?

Обновление: Если описанный выше подход осуществим, проблема сводится к выходу из цикла и нахождению не посещенного цикла. Я могу узнать, посещается ли цикл, сохранив номер, в котором наши указатели встречаются изначально. Так что технически занимаем O(k) место для k дубликатов. Поиск другого цикла можно было бы выполнить с помощью рандомизированного запуска и проверки, посещен ли цикл или нет. Но по мере приближения числа найденных дубликатов k рандомизированный запуск будет замедляться и может никогда не завершиться. Кроме того, существует ли какой-либо разумный способ выбрать индекс для рандомизированного подхода, чтобы он гарантировал завершение?

Комментарии:

1. Я не думаю, что вам нужно хранить первый - запуск в O(N). Просто запустите модифицированную версию алгоритма, где каждый посещенный узел помечен (реализация зависит от вас) таким образом, чтобы можно было восстановить его исходное значение. После выполнения первой итерации перейдите к следующему узлу,который не был отмечен, запустите модифицированный алгоритм; не забудьте сопоставить исходное значение для отмеченных узлов, чтобы определить соседей. Он все равно будет работать в O(2N) = O(N) времени (почему?) и явно использует O(1) пространство. После достижения конца снимите пометки со всех отмеченных узлов, чтобы восстановить исходный массив.

2. @wLui155 Я пропустил требование, чтобы массив не мог быть изменен, если вы предлагаете, чтобы я связывал логические значения с каждым индексом массива. Поэтому я не могу отметить это. Создание другого массива для хранения логических значений mark/unmark потребует дополнительной памяти.

3. Хм, это немного усложняет ситуацию — это то, что массив читается только для начала? Метод, о котором я думал, восстановит его, но если это невозможно, то мой предложенный подход не сработает.

4. С другой стороны, даже если бы я мог изменить массив, как я буду отмечать их, сохраняя дальнейшие проходы алгоритма в пределах одного и того же циклического пути?

5. Чтобы отменить узел в индексе i вашего массива A , просто назначьте -A[i] A[i] if A[i] > 0 ему . Хорошая вещь в отрицании заключается в том, что функция абсолютного значения даст исходное значение (которое гарантированно было положительным). Таким образом, вы, по сути, кодируете два состояния внутри одного узла в постоянной памяти — независимо от того, посещен он или нет (положительный/отрицательный) и сосед (абсолютное значение сохраненного значения). Например, если у нас есть входной массив [4, 2, 1, 2, 1] и он проиндексирован на 0, вы бы запустили алгоритм с индексом 0 и в итоге получили [-4, -2, -1, 2, -1] , где 1 находится дубликат.

Метки: ,