O (n) для нахождения нечетного числа в массиве последовательных целых чисел от 1 до n (нечетные числа)

У меня много проблем, пытаясь понять этот вопрос, и корень этой проблемы создает алгоритм сложности O(n). Вот вопрос, с которым я борюсь:

Array A длины n содержит целые числа из диапазона [0, .., n - 1]. Однако он содержит только n - 1 различные числа. Поэтому одно из чисел отсутствует, а другой номер дублируется. Напишите метод Java, который принимает A как входной аргумент и возвращает недостающее число; метод должен работать в O(n).

Например, когда A = [0, 2, 1, 2, 4], oddOneOut() должен возвращать 3; когда A = [3, 0, 0, 4, 2, 1], oddOneOut() должен возвращать 5.

Очевидно, что это простая задача для решения с помощью алгоритма O(n²) (и, скорее всего, O(n), я просто этого не вижу!). Я попытался решить эту проблему, используя всевозможные методы, но безрезультатно. Я пытаюсь решить эту проблему на Java, но если вы более комфортно решаете ее на Python, это тоже будет хорошо.

Спасибо заранее...

Ответ 1

Предположим, что число отсутствует x, а дубликат - y. Если вы добавите все числа, сумма будет:

(n - 1) * n / 2 - x + y

Из вышесказанного вы можете найти (x - y)..... (1)

Аналогично суммируем квадраты чисел. Тогда сумма будет:

(n - 1) * n * (2 * n - 1) / 6 - x² + y²

Из вышесказанного вы получите (x² - y²).... (2)

(2) / (1) gives (x + y).....(3)

(1) + (3) дает 2 * x, и вы можете найти x и y.

Обратите внимание, что в этом решении есть O(1) дополнительное хранилище и O(n) временная сложность. Другие вышеприведенные решения не требуют дополнительного хранения O(n).

Код в смешанном C/С++ для большей ясности:

#include <stdio.h>

int findDup(int *arr, int n, int& dup, int& missing)
{
    int sum = 0;
    int squares = 0;

    for (int i = 0; i < n; i++) {
        sum += arr[i];
        squares += arr[i] * arr[i];
    }

    sum = (n - 1) * n / 2 - sum; // x - y

    squares = (n - 1) * n * (2 * (n - 1) + 1) / 6 - squares; // x^2 - y^2

    if (sum == 0) {
        // no duplicates
        missing = dup = 0;
        return -1;
    }
    missing = (squares / sum + sum) / 2; // ((x^2 - y^2) / (x - y) + (x - y)) / 2 = ((x + y) + (x - y)) / 2 = x

    dup = missing - sum; // x - (x - y) = y

    return 0;
}


int main(int argc, char *argv[])
{
    int dup = 0;
    int missing = 0;

    int a[] = {0, 2, 1, 2, 4};

    findDup(a, sizeof(a) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    int b[] = {3, 0, 0, 4, 2, 1};
    findDup(b, sizeof(b) / sizeof(int), dup, missing);
    printf("dup = [%d], missing = [%d]\n", dup, missing);

    return 0;
}

Вывод:

dup = [2], missing = [3]
dup = [0], missing = [5]

Некоторые коды python:

def finddup(lst):
    sum = 0
    sumsq = 0
    missing = 0
    dup = 0
    for item in lst:
        sum = sum + item
        sumsq = sumsq + item * item
    n = len(a)
    sum = (n - 1) * n / 2 - sum
    sumsq = (n - 1) * n * (2 * (n - 1) + 1) / 6 - sumsq
    if sum == 0:
        return [-1, missing, dup]
    missing = ((sumsq / sum) + sum) / 2
    dup = missing - sum
    return [0, missing, dup]

found, missing, dup = finddup([0, 2, 1, 2, 4])
if found != -1:
    print "dup = " + str(dup) + " missing = " + str(missing)

print finddup([3, 0, 0, 4, 2, 1])

Выходы:

dup = 2 missing = 3
[-1, 0, 0]

Ответ 2

Итерации по массиву дважды: это все равно O (n). Создайте временный массив логических элементов (или Java BitSet), чтобы сохранить номера, которые вы получили. Второй раз, когда вы делаете цикл, проверьте, есть ли в массиве логических элементов отверстие.

Ответ 3

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

Теперь вычислите ожидаемое значение, если все числа были разными: n * (n - 1) / 2. Вычтите итог, который вы нашли. Вы останетесь с "отсутствующим" числом минус дубликат. Добавьте дубликат, чтобы получить ответ.

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

Ответ 4

Это может представлять интерес, хотя я не уверен, при каких условиях (если они есть) он лучше всего работает. Идея состоит в том, что мы переместим каждый элемент в правильное место в массиве (0 в индекс 0 и т.д.), Пока не станет ясно, чего не хватает и что дополнительно.

def findmissing(data):
    upto = 0
    gap = -1
    while upto < len(data):
        #print data, gap
        if data[upto] == upto:
            upto += 1
            continue
        idx = data[upto]
        if idx is None:
            upto += 1
            continue
        data[upto], data[idx] = data[idx], data[upto]
        if data[upto] == data[idx]:
            print 'found dupe, it is', data[upto]
            data[upto] = None
            gap = upto
            upto += 1
        elif data[upto] is None:
            gap = upto
    return gap

if __name__ == '__main__':
    data = range(1000)
    import random
    missing = random.choice(data)
    print missing
    data[missing] = data[0]
    data[0] = random.choice(data[1:])
    random.shuffle(data)
    print 'gap is', findmissing(data)

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