Интересная проблема.
Если массив состоит из целых чисел со знаком, я полагаю, что это возможно во времени O (n) и в пространстве O (1), без переполнений, при условии, что длина достаточно мала, чтобы это могло произойти.
Основная идея заключается в следующем:
У нас есть n номеров. Теперь, разделив эти числа на n + 1, мы получим n остатков. Таким образом, по крайней мере один из остатков в {0,1,2, ..., n} должен отсутствовать (скажем, г). Мы заполняем массив числами, остатки которых равны r.
Сначала мы добавляем кратное n + 1 ко всем отрицательным числам, чтобы сделать их положительными.
Далее мы проходим массив и находим остаток каждого числа с помощью n + 1. Если остаток равен r, мы устанавливаем a [r] равным -a [r], если a [r] был положительным. (Если мы встречаем отрицательные числа при ходьбе, мы используем отрицательную версию при взятии остатка).
У нас также есть дополнительный int для остаток = n.
В конце мы снова обходим массив, чтобы увидеть, есть ли какие-либо положительные числа (будет одно, или дополнительное значение int для остаток = n будет не установлено).
Как только у нас есть остаток, легко сгенерировать n чисел с этим остатком. Конечно, мы всегда можем сгенерировать только одно число и заполнить его этим, поскольку проблема никогда не говорила об уникальных числах.
Если бы массив состоял из целых чисел без знака, мы могли бы , вероятно, , по-прежнему делать это с лучшим ведением учета.
Например, мы могли бы попытаться использовать первые целые числа n / logn в качестве нашего битового массива, чтобы указать, какие остатки были замечены, и использовать некоторые дополнительные целые числа O (1) для временного хранения чисел.
Например, вы делаете tmp = a [0], находите остаток и устанавливаете соответствующий бит [0] (предварительно установив его в ноль). tmp = a [1], установить бит и т. д. Мы никогда не будем перезаписывать число до того, как оно нам понадобится, чтобы найти его остаток.