Для данного массива с несколькими повторяющимися записями, fnd одна повторная запись O (N) время и постоянное пространство

Question

Нам дан массив размером N, который содержит целые числа в диапазоне от 0 до N-2, оба включительно.

Массив может иметь несколько повторяющихся записей. Нам нужно найти одну из дублированных записей в O (N) времени и постоянном пространстве.

Я думал о том, чтобы взять произведение и сумму всех чисел в массиве, а также произведение и сумму всех чисел в диапазоне от 0 до N-2.

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

Есть предложения?

Редактировать: массив является неизменным. Я понимаю, что это важная часть информации, и я прошу прощения, что забыл включить это ранее.

Answer 1

Вот хорошее лечение. Перед решением этой проблемы он проходит через несколько простых проблем.

http://aperiodic.net/phil/archives/Geekery/find-duplicate-elements.html

Содержит решение, когда вы можете изменить входной массив, и другое, когда вы не можете.

Краткое описание на случай, если ссылка когда-либо прекратится: индексы массива начинаются с 0 .. N-1, а значения массива - 0 .. N-2. Поэтому каждый элемент массива можно рассматривать как индекс (или «указатель») в самом массиве: элемент i «указывает на» элемент ra[i], ra[i] указывает на ra[ra[i]] и т. Д. Повторно следуя этим указателям, я должен в конечном итоге войти в цикл, потому что мы определенно не можем идти вечно, не повторно посетив тот или иной узел.

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

  N-1 -> a1 -> a2 -> a3
               ^       \
              /         v
            a6 <- a5 <- a4

В этом случае a2 доступен из двух разных мест.

Но узел, который доступен из двух разных мест, это именно то, что мы ищем, дубликат в массиве (два разных элемента массива, содержащие одно и то же значение).

Тогда возникает вопрос, как определить a2, и ответом является использование Алгоритма Флойда для нахождения цикла . В частности, он сообщает нам «начало» цикла в O (N) времени и O (1) пространстве.

Answer 2

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

a = array...
for i = 0; i < length(a); i++
  curr = a[i]
  if a[curr] == curr:
    return duplicate curr
  swap(a[i], a[curr])
  # Now a[curr] == curr and so if it happens again we know it is a duplicate. 

Это будет O (n) и постоянный пробел.

Answer 3

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

Answer 4

Инициализируйте битовый массив размера N-2 со всеми записями равным 0. Каждый индекс будет представлять все ваши элементы в диапазоне от 0 до N-2.

Переберите свой массив и добавьте элементы в ваш битрейр, установив bitarray[number] == 1. Если элемент уже содержит 1, значит, вы уже добавили свой элемент, немедленно вернитесь.

Если вы дошли до конца массива, не найдя дубликат, верните -1. ​​

Answer 5

Сканирование массива и добавление каждого элемента в набор. Если предмет уже существует в наборе - у вас есть дубликаты.

Answer 6

(извините, еще не могу комментировать ....)

@ Blastfurnace ах .. хороший улов, что для циклов сначала нужно проверить

if a[i] == i:
  continue  # Don't swap with yourself!

Если массив неизменен, тоВы можете просто сохранить следующие элементы, т.е. пропустить, пока a [i] == i, затем из [i] перейти к [a [i]].Это попадет в петлю, и тогда мы сможем использовать решение «как обнаружить петлю в связанном списке» (держите 2 указателя, один перемещается со скоростью 1, другой - 2, и когда они оба встретятся, вы знаете, что вы попали в цикл).

Если мы можем изменить массив и затем вернуть его без изменений, тогда мы можем обмануть :) Из i = 0, превратить a [a [i]] в отрицательное целое число, если оно еще не существует, если оно уже отрицательно, тогда мы знаемэтот элемент a [i] был посещен дважды.Перед возвратом верните все негативы в позитивы (для 0 используйте MIN_INT)

Answer 7

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

HashSet hSet = new HashSet();

for(int i = 0; i < array.length(); i++){    
    if(hSet.contains(array[i])
       return array[i];
    else
       hSet.add(array[i]);
}
return -1;

хотя я не уверен, что это удовлетворит ваши требования к памяти, предыдущий пост extraneon с сортировкой по месту со вторым ходом может быть больше, чем вы ищете