Как найти повторяющийся элемент в неупорядоченном массиве, используя константное пространство
Я просматриваю экзаменационные вопросы и наткнулся на этот, который не могу решить (10.а).
Поскольку я не могу изменить массив, я знаю, что не могу использовать сортировку пузырьком, например, но бит, который меня бросает, - это "не зависит от п", единственная идея, которую я могу придумать, - это выбрать элемент array[i] и сравнить его с array[i+j] который Я понимаю, что это запрещено, так как это зависит от n.
Мы несколько человек в нашем курсе ломаем головы над тем, как нам подойти к этому, кто-нибудь может дать нам представление о том, как его решить?
Для второй части у нас все в порядке, поскольку мы сделали несколько алгоритмов поиска, которые могли бы решить вопрос.
При сравнении элементов входного массива не требуется дополнительное пространство.
Для 10a вы должны использовать очевидный алгоритм O (n ^ 2), т. Е. Проверять каждую пару. Для 10b вы должны сначала сортировать, а затем искать соседние дубликаты или использовать хеш-таблицу или другую структуру индексации.
Да, извините, я имел в виду массив [i+j], тогда я сбиваюсь с толку относительно того, что означает «постоянное количество дополнительного пространства, не зависящее от n», поскольку я думал, что он имел в виду, что нам в основном не разрешено выполнять линейный поиск
Ответы 1
may use only a constant amount of additional space
Это означает, что вашему алгоритму разрешено использовать только фиксированное количество ячеек памяти. Однако это не означает, что вам запрещен доступ к памяти, содержащей входной массив.
Обратите внимание, что вопрос касается константы пространство, а не константы время.
Решение, которое сравнивает каждый array[i] с array[i+j], вполне приемлемо, поскольку для него требуется только 1 дополнительная ячейка памяти (для хранения результата).
То есть в основном нет рекурсии или вызовов стека?
@Sergi: Рекурсия все еще может быть в порядке, если ее потребление стека не зависит от размера массива n. Это случай хвостовой рекурсии (которую можно эффективно переписать в цикл).
"элемент массива [i] и сравнить его с массивом [i+n]" - если вы имеете в виду массив [i+j], то да, это ответ, и он разрешен, потому что пространство не зависит от n*. Как вы думаете, почему это будет зависеть от n?