Вопрос о семье

Ответ 1

Вопрос немного неоднозначен; когда запрос "какой", означает ли это возвращение дублирующегося значения или положение в последовательности дублированного? Если первое, любое из следующих трех решений будет работать; если это последняя, ​​первая будет единственной, которая поможет.

Решение №1: предполагает, что массив является неизменным

Построить растровое изображение; установите n-й бит, когда вы перебираете массив. Если бит уже установлен, вы нашли дубликат. Он работает по линейному времени и будет работать для любого массива размера.

Растровое изображение будет создано с таким количеством бит, как в массиве возможны значения. Когда вы перебираете массив, вы проверяете n-й бит в массиве. Если он установлен, вы нашли свой дубликат. Если это не так, установите его. (Логику для этого можно увидеть в псевдокоде в этой записи в Википедии Бит-массивы или использовать System.Collections.BitArray class.)

Решение № 2: предполагается, что массив изменен

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

Решение №3: (предполагает длину массива = 1000,001)

• Суммировать все целые числа в массиве.
• Из этого вычтите сумму целых чисел от 1 до 1000000 включительно.
• Остальное будет вашим дублированным значением.

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

Недостаток заключается в том, что вам нужно выполнить весь цикл, чтобы найти ответ.

Преимущества - это простота и высокая вероятность того, что он будет работать быстрее других решений.

Ответ 2

Предполагая, что все числа от 1 до 1 000 000 находятся в массиве, сумма всех чисел от 1 до 1 000 000 равна (1,000,000)*(1,000,000 + 1)/2 = 500,000 * 1,000,001 = 500,000,500,000.

Итак, просто добавьте все числа в массиве, вычтите 500 000 500 000, и вы останетесь с числом, которое произошло дважды.

O (n) и O (1) памяти.

Если предположение неверно, вы можете попробовать использовать Bloom Filter - их можно много хранить более компактно, чем хеш-таблица (поскольку они хранят только факт присутствия), но они рискуют ложными срабатываниями. Этот риск может быть ограничен, хотя, по нашему выбору, сколько памяти нужно потратить на фильтр цветения.

Затем мы можем использовать фильтр цветения для обнаружения потенциальных дубликатов в O (n) времени и проверять каждый кандидат в O (n) времени.

Ответ 3

Этот код python представляет собой модификацию QuickSort:

def findDuplicate(arr):
    orig_len = len(arr)
    if orig_len <= 1:
        return None
    pivot = arr.pop(0)
    greater = [i for i in arr if i > pivot]
    lesser = [i for i in arr if i < pivot]
    if len(greater) + len(lesser) != orig_len - 1:
        return pivot
    else:
        return findDuplicate(lesser) or findDuplicate(greater)

Он находит дубликат в O (n logn)), я думаю. Он использует дополнительную память в стеке, но ее можно переписать для использования только одной копии исходных данных. Я полагаю:

def findDuplicate(arr):
    orig_len = len(arr)
    if orig_len <= 1:
        return None
    pivot = arr.pop(0)
    greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
    lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
    if len(arr):
        return pivot
    else:
        return findDuplicate(lesser) or findDuplicate(greater)

Перечисления списков, которые приводят к большему и меньшему уничтожению оригинала вызовами pop(). Если arr не пуст после удаления большего и меньшего от него, тогда должен быть дубликат, и он должен быть поворотным.

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

def findDuplicate(full):
    import copy
    q = [full]
    while len(q):
        arr = copy.copy(q.pop(0))
        orig_len = len(arr)
        if orig_len > 1:
            pivot = arr.pop(0)
            greater = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] > pivot]
            lesser = [arr.pop(i) for i in reversed(range(len(arr))) if arr[i] < pivot]
            if len(arr):
                return pivot
            else:
                q.append(greater)
                q.append(lesser)
    return None

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

Так много для информатики. Наивный алгоритм сжимает мой код в python, возможно, из-за алгоритма сортировки python:

def findDuplicate(arr):
    arr = sorted(arr)
    prev = arr.pop(0)
    for element in arr:
        if element == prev:
            return prev
        else:
            prev = element
    return None

Ответ 4

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

например. Реализация сортировки слияния на месте.

http://en.wikipedia.org/wiki/Merge_sort

Ответ 5

Подсказка: используйте свойство A XOR A == 0 и 0 XOR A == A.

Ответ 6

В качестве варианта вашего решения (2) вы можете использовать сортировку radix. Нет дополнительной памяти, и она будет работать в линейное время. Вы можете утверждать, что на время также влияет размер представления чисел, но вы уже дали оценку для этого: сортировка radix выполняется во времени O (k n), где k - количество цифр, которые вы можете сортировать в каждом проходе. Это делает весь алгоритм O (7n) для сортировки плюс O (n) для проверки дублированного числа - это O (8n) = O (n).

Плюсы:

• Нет дополнительной памяти
• О (п)

Минусы:

• Нужно пройти восемь O (n).

Ответ 7

А как насчет проблемы поиска ВСЕХ дубликатов? Можно ли это сделать менее чем O (n ln n) время? (Сортировка и сканирование) (Если вы хотите восстановить исходный массив, поместите исходный индекс и измените порядок после конца, что можно сделать в O (n) времени)

Ответ 8

def singleton(array):
  return reduce(lambda x,y:x^y, array)

Ответ 9

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

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