Найдите элемент, встречающийся один раз в массиве, где все остальные элементы встречаются дважды (без использования XOR)

Question

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

Для массива n чисел, в котором все числа встречаются дважды, кроме одного, которое встречается только один раз, найдите число, которое встречается только один раз.

Теперь я нашел в Интернете много решений для этого, но ни одно из них не удовлетворяет дополнительным ограничениям вопроса. Решение должно:

• Запуск в линейное время (также известный как O (n)).
• Не использовать таблицы ha sh.
• Предположим, что компьютер поддерживает только сравнение и арифметические операции. c (сложение, вычитание, умножение, деление).
• Количество бит в каждом числе в массиве составляет примерно O (log (n)).

Следовательно, попытаться сделать что-то вроде этого { ссылка } с использованием оператора XOR невозможно, поскольку у нас нет оператора XOR. Поскольку количество бит в каждом числе составляет около O (log (n)), попытка реализовать оператор XOR с использованием обычной арифметики c (побитно) потребует примерно O (log (n)) действий, что даст нам общее решение O (nlog (n)).

Ближе всего к решению этой проблемы я подошел, если бы у меня был способ получить сумму всех уникальных значений в массиве за линейное время, я мог бы дважды вычесть эту сумму из общей суммы, чтобы получить (отрицательное) элемент, который встречается только один раз, потому что если числа, которые появляются дважды, это {a1, a2, ...., ak}, а число, которое появляется один раз, это x, то общая сумма равна сумма = 2 (a1 + ... + ak) + x Насколько мне известно, наборы реализованы с использованием таблиц ha sh, поэтому использовать их для нахождения суммы всех уникальных значений бесполезно.

Answer 1

Давайте представим, что у нас есть способ найти точную медиану за линейное время и разделить массив так, чтобы все большие элементы находились с одной стороны, а меньшие - с другой. По четности ожидаемого количества элементов мы могли определить, на какой стороне находится целевой элемент. Теперь выполните эту процедуру рекурсивно в идентифицированном разделе. Поскольку размер секции каждый раз уменьшается вдвое, общее количество пройденных элементов не может превышать O (2n) = O (n).

Answer 2

Ключевым элементом в вопросе кажется следующий:

Количество бит в каждом числе в массиве составляет около O (log (n)).

Проблема в том, что эта подсказка немного расплывчата.

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

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

C[a[i]]++;

Поиск нечетного значения в массиве C[] предоставит решение.

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

C[a[i]%n].append (a[i]);

Чтобы найти уникальный элемент, мы должны найти подмассив нечетного размера, а затем исследовать элементы в этом под- массив.

Максимальный размер k каждого подмассива будет около 2 * (MAX / n). Согласно подсказке, это значение должно быть очень низким. Работа с этим подмассивом имеет сложность O (k), например, путем выполнения сортировки с подсчетом на b[j]/n, все элементы равны по модулю n.

Мы можем заметить, что практически это эквивалентно выполнению своего рода специального хеширования c.

Глобальная сложность O (n + MAX / n).

Answer 3

Вот (неоптимизированная) реализация идеи, набросанной גלעד ברקן. Я использую Median_of_medians , чтобы получить значение, достаточно близкое к медиане, чтобы обеспечить линейное время в худшем случае.

NB: на самом деле здесь используются только сравнения, и это O (n ) независимо от размера целых чисел, пока сравнения и копии считаются как O (1).

def median_small(L):
    return sorted(L)[len(L)//2]

def median_of_medians(L):
    if len(L) < 20:
        return median_small(L)
    return median_of_medians([median_small(L[i:i+5]) for i in range(0, len(L), 5)])

def find_single(L): 
    if len(L) == 1: 
        return L[0] 
    pivot = median_of_medians(L) 
    smaller = [i for i in L if i <= pivot] 
    bigger =  [i for i in L if i > pivot] 
    if len(smaller) % 2: 
        return find_single(smaller) 
    else: 
        return find_single(bigger)

Эта версия требует дополнительного пространства O (n), но может быть реализована с помощью O (1).

Answer 4

Это должно сработать, если вы имеете дело с целыми числами размера O(log n). Это Python реализация набросанного алгоритма @ גלעד רקן answer (включая комментарии @OneLyner), где медиана заменена средним или средним значением.

def mean(items):
    result = 0
    for i, item in enumerate(items, 1):
        result = (result * (i - 1) + item) / i
    return result


def midval(items):
    min_val = max_val = items[0]
    for item in items:
        if item < min_val:
            min_val = item
        elif item > max_val:
            max_val = item
    return (max_val - min_val) / 2


def find_singleton(items, pivoting=mean):
    n = len(items)
    if n == 1:
        return items[0]
    else:
        # find pivot - O(n)
        pivot = pivoting(items)
        # partition the items - O(n)
        j = 0
        for i, item in enumerate(items):
            if item > pivot:
                items[j], items[i] = items[i], items[j]
                j += 1
        # recursion on the partition with odd number of elements
        if j % 2:
            return find_singleton(items[:j])
        else:
            return find_singleton(items[j:])

Следующий код предназначен только для проверки работоспособности случайных входных данных:

def gen_input(n, randomize=True):
    """Generate inputs with unique pairs except one, with size (2 * n + 1)."""
    items = sorted(set(random.randint(-n, n) for _ in range(n)))[:n]
    singleton = items[-1]
    items = items + items[:-1]
    if randomize:
        random.shuffle(items)
    return items, singleton


items, singleton = gen_input(100)
print(singleton, len(items), items.index(singleton), items)
print(find_singleton(items, mean))
print(find_singleton(items, midval))

Для симметричного c распределения медиана и среднее или среднее значение совпадают. С помощью требования log (n) к количеству битов для записей можно показать, что любая произвольная подвыборка не может быть искажена настолько, чтобы обеспечить более log(n) рекурсий.

Например, учитывая случай k = log (n) битов с k = 4 и только положительными числами, наихудший случай: [0, 1, 1, 2, 2, 4, 4, 8, 8, 16, 16]. Здесь поворот по среднему будет уменьшать ввод на 2 за раз, что приводит к k + 1 рекурсивным вызовам, но добавление любой другой пары ко входным данным не увеличит количество рекурсивных вызовов, но увеличит размер ввода.

(ОТредактировано для лучшего объяснения.)