Как найти дубликаты в массиве за O (1) раз в Java? - PullRequest
Новая
       51

Как найти дубликаты в массиве за O (1) раз в Java?

0 голосов
/ 18 июня 2019

Мне дано задание найти дубликаты в массиве int за O (1) раз. Мой подход состоит в том, чтобы сначала отсортировать массив, а затем найти дубликаты, используя линейный поиск. Сначала я использовал сортировку массива путем замены чисел следующим образом: 

for(int i = 0;i<ar.length;i++) {
    for (int j = i + 1; j < ar.length; j++) {
        if (ar[i] > ar[j]) {
            buk = ar[i];
            ar[i] = ar[j];
            ar[j] = buk;
        }
    }
}

, но эффективность этого алгоритма составляет O (i * j) , что не требуется для решения. Я попытался использовать рекурсию для сортировки массива: 

static int x = 0;
static int[] swap(int[] arr) {
    if (x >= arr.length)
        return arr;
    for (int i = 1; i < arr.length; i++) {
        if (arr[i - 1] > arr[i]) {
            int bucket = arr[i - 1];
            arr[i - 1] = arr[i];
            arr[i] = bucket;
        }
    }
    x++;
    arr = swap(arr);
    return arr;
}

Но, похоже, сейчас это не работает. Пожалуйста, предоставьте предложения / альтернативные методы для сортировки массива, я сталкивался с этой проблемой много раз.

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

1 Ответ

4 голосов
/ 18 июня 2019

Математически невозможно найти дубликаты в O(1). Вы должны проверить все N элементы массива хотя бы один раз , чтобы проверить, является ли каждый из них дубликатом. Это не менее N операций, поэтому нижняя граница сложности составляет O(N).

Подсказка: вы можете сделать это в O(N), если вы используете (скажем) HashSet для записи каждого значения, которое вы уже видели. Загвоздка в том, что HashSet является пространственно-ориентированной структурой данных.

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

Простой способ сортировки массива целых чисел - использовать Arrays::sort(int[]). Это будет O(NlogN).

Теоретически возможно отсортировать массив целых чисел лучше, чем O(NlogN), но только если вы можете поместить границу в диапазон целого числа. Поиск вверх подсчет сортировки . Сложность составляет O(max(N, R), где R - это разница между наименьшим и наибольшим числом. Подвох в том, что O(R) может быть намного больше, чем O(N) ... в зависимости от входных данных.

Но если вы знаете, что M, вероятно, будет меньше, чем NlogN, вы можете использовать вариант сортировки счетчиков и использовать только O(M) бит дополнительного пространства для дедупликации массива в O(max(M, N)). (Я оставлю вас, чтобы выяснить детали.)

...