Поиск повторяющихся целых чисел со знаком O (n) во времени и O (1) в пространстве

Ответ 1

Определение записи с большими выводами состоит в том, что его аргумент является функцией (f (x)), что, поскольку переменная в функции (x) стремится к бесконечности, существует константа K такая, что объектная функция стоимости будет быть меньше, чем Kf (x). Обычно f выбирается как наименьшая такая простая функция, что условие выполняется. (Очень очевидно, как поднять вышеперечисленное до нескольких переменных.)

Это связано с тем, что K - который вы не обязаны указывать - позволяет скрывать скрытое целое множество сложного поведения. Например, если ядром алгоритма является O (n ²), он допускает всевозможные другие O (1), O (logn), O (n), O (nlogn), O (n ^3/2) и т.д. поддерживающие биты должны быть скрыты, даже если для реалистичных входных данных эти части являются фактически доминирующими. Правильно, это может быть совершенно неверно! (Некоторые из алгоритмов fancier bignum обладают этим свойством для реального. Ложь с математикой - замечательная вещь.)

Итак, где это происходит? Ну, вы можете предположить, что int является фиксированным размером достаточно легко (например, 32-разрядным) и использует эту информацию, чтобы пропустить много проблем и выделить массивы фиксированного размера бит флага для хранения всей необходимой вам информации. Действительно, используя два бита на потенциальное значение (один бит, чтобы сказать, видели ли вы значение вообще, другое - сказать, напечатали ли вы его), тогда вы можете обрабатывать код с фиксированным объемом памяти размером 1 ГБ. Это даст вам достаточно информации о флагах, чтобы справиться с таким количеством 32-битных целых чисел, как вы когда-либо хотели бы справиться. (Heck, что даже практично на 64-битных машинах.) Да, потребуется некоторое время, чтобы установить этот блок памяти вверх, но он постоянный, так что формально O (1) и так выпадает из анализа. Учитывая это, у вас тогда есть постоянное (но колоссальное) потребление памяти и линейное время (вам нужно посмотреть каждое значение, чтобы увидеть, было ли оно новым, увиденным один раз и т.д.), Что именно то, что было предложено.

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

[EDIT] Пример кода C (это не С++, но я не очень хорошо разбираюсь в С++, основное отличие будет в том, как выделяются и управляются массивы флагов):

#include <stdio.h>
#include <stdlib.h>

// Bit fiddling magic
int is(int *ary, unsigned int value) {
    return ary[value>>5] & (1<<(value&31));
}
void set(int *ary, unsigned int value) {
    ary[value>>5] |= 1<<(value&31);
}

// Main loop
void print_repeats(int a[], unsigned size) {
    int *seen, *done;
    unsigned i;

    seen = calloc(134217728, sizeof(int));
    done = calloc(134217728, sizeof(int));

    for (i=0; i<size; i++) {
        if (is(done, (unsigned) a[i]))
            continue;
        if (is(seen, (unsigned) a[i])) {
            set(done, (unsigned) a[i]);
            printf("%d ", a[i]);
        } else
            set(seen, (unsigned) a[i]);
    }

    printf("\n");
    free(done);
    free(seen);
}

void main() {
    int a[] = {1,0,-2,4,4,1,3,1,-2};
    print_repeats(a,sizeof(a)/sizeof(int));
}

Ответ 2

Поскольку у вас есть массив целых чисел, вы можете использовать прямое решение с сортировкой массива (вы не сказали, что его нельзя изменить) и печать дубликатов. Целочисленные массивы могут быть отсортированы с сложностями времени и пространства O (n) и O (1) с использованием Radix sort. Хотя, вообще говоря, это может потребовать O (n) -пространства, бинарная сортировка двоичных MSD-оснований может быть реализована тривиально с использованием O (1) пространства (посмотрите здесь для получения дополнительной информации подробнее).

Ответ 3

Ограничение пространства O (1) является неразрешимым.

Сам факт печати самого массива требует, по определению, O (N) хранения.

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

Тем не менее, ограничение пространства O (1) кажется неустранимым из-за ограничения неизменяемости входного массива. Возможно, это не так, но это так.

И ваше решение переполняется, потому что вы пытаетесь запомнить информацию O (N) в конечном типе данных.

Ответ 4

Здесь есть сложная проблема с определениями. Что означает O (n)?

Константин отвечает, что сложность времени сортировки по методу Radix равна O (n). На самом деле это O (n log M), где базой логарифма является выбранный радикс, а M - диапазон значений, которые могут иметь элементы массива. Так, например, двоичный радиальный вид 32-битных целых чисел будет иметь log M = 32.

Итак, это по-прежнему, в некотором смысле, O (n), потому что log M является константой, не зависящей от n. Но если мы допустим это, то существует гораздо более простое решение: для каждого целого числа в диапазоне (все из них 4294967296) пройдите через массив, чтобы увидеть, происходит ли это более одного раза. Это также, в известном смысле, O (n), потому что 4294967296 также является константой, не зависящей от n.

Я не думаю, что мое простое решение будет считаться ответом. Но если нет, то мы также не должны допускать сортировку radix.

Ответ 5

Я действительно не вижу, как вы можете иметь только O (1) пространство, а не изменять исходный массив. Я предполагаю, что вам нужна дополнительная структура данных. Например, каков диапазон целых чисел? Если это 0..N, как в другом связанном вами вопросе, вы можете иметь дополнительный массив count N. Затем в O (N) пересечь исходный массив и прирастить счетчик в позиции текущего элемента. Затем перейдите к другому массиву и напечатайте цифры с помощью count >= 2. Что-то вроде:

int* counts = new int[N];
for(int i = 0; i < N; i++) {
    counts[input[i]]++;
}

for(int i = 0; i < N; i++) {
    if(counts[i] >= 2) cout << i << " ";
}

delete [] counts;

Ответ 6

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

Без потери общности можно сказать, что мы обрабатываем массив k раз, где k фиксировано. Решение также должно работать, когда имеется m дубликатов, с m → k. Таким образом, по крайней мере в одном из проходов мы должны иметь возможность выводить x дубликатов, где x растет, когда m растет. Для этого некоторая полезная информация была вычислена в предыдущем проходе и сохранена в хранилище O (1). (Сам массив не может быть использован, это даст O (n) хранилище.)

Проблема: у нас есть O (1) информации, когда мы ходим по массиву, мы должны идентифицировать числа x (для их вывода). Нам нужно хранилище O (1), которое может сказать нам в O (1) раз, если в нем находится элемент. Или, по-другому, нам нужна структура данных для хранения n булевых (из которых x являются true), которые используют O (1) пространство и берут O (1) время для запроса.

Имеется ли эта структура данных? Если нет, то мы не можем найти все дубликаты в массиве с O (n) временем и O (1) пространством (или есть какой-то фантастический алгоритм, который работает совершенно по-другому???).

Ответ 7

Скажите, что вы можете использовать тот факт, что вы не используете все пространство, которое у вас есть. Вам нужно только один бит за возможное значение, и у вас много неиспользуемого бита в ваших 32-битных значениях int.

Это имеет серьезные ограничения, но работает в этом случае. Числа должны быть между -n/2 и n/2, и если они повторяют m раз, они будут напечатаны m/2 раза.

void print_repeats(long a[], unsigned size) {
    long i, val, pos, topbit = 1 << 31, mask = ~topbit;
    for (i = 0; i < size; i++)
        a[i] &= mask;

    for (i = 0; i < size; i++) {
        val = a[i] & mask;
        if (val <= mask/2) {
           pos = val;
        } else {
            val += topbit;
            pos = size + val;
        }
        if (a[pos] < 0) {
            printf("%d\n", val);
            a[pos] &= mask;
        } else {
            a[pos] |= topbit;
        }
    }
}

void main() {
    long a[] = {1, 0, -2, 4, 4, 1, 3, 1, -2};
    print_repeats(a, sizeof (a) / sizeof (long));
}

печатает

4
1
-2