Поиск первого дубликата в массиве int, java

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

assume we have an int array int[] A, we want to find the first duplicate entry.

  • почти каждый может подумать об использовании HashSet и добавить к нему во время разбора. Это приведет к времени O (n) и O (n). После этого меня попросили решить его без других структур данных. Я сказал, что самая туманная идея будет сравнивать каждую в O (n ^ 2) времени. И затем меня попросили улучшить время O (n ^ 2).

  • И чтобы улучшить его, я подумал об использовании массива фиксированного размера (при условии, что максимальное число равно n), boolean [] b = new boolean [n]; однако мне не разрешили использовать этот метод.

  • Затем я подумал об использовании переменной int, используя манипуляции с битами, если максимальное число меньше 32, тогда для n мы можем нажать 1 на n бит влево и | к контролеру, затем и контролеру к следующей записи в массиве, чтобы проверить, > ли это > 0. например:.

    int c = A[i];
if(check & (1 << c) > 0) return false;
check |= 1 << c;

однако это также не допускается.

Итак, был намек на то, что я могу использовать сам массив как hashset/hashtable и "линейное хеширование"?

любая помощь? спасибо

Ответы

Ответ 1

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

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

Таким образом, этот алгоритм не дает лучшей асимптотической пространственной сложности, чем обычный HashSet. Тем не менее, это уменьшает потребление памяти на постоянный коэффициент.

Его временная сложность находится на одном уровне с обычным HashSet.

Изменить: Мне кажется, что этот ответ игнорируется (нет голосов, нет комментариев). Разве это не полезно? Прошу прокомментировать, поэтому я знаю, что улучшить.

Ответ 2

У меня есть эта идея: по мере продвижения по массиву вы сортируете ту часть, которую вы посетили. Используя бинарный поиск, вы улучшите время; пространство равно 0. Сорт сам по себе... insertion sort? Вы в основном используете сортировку как обычно, но при поиске места для вставки нового numeber, если вы нажмете на номер, вы будете кричать "bingo". Это улучшение по сравнению с нулевым пространством + O (n 2).

Ответ 3

Я бы попросил интервьюера (-ов), почему они не хотят, чтобы вы использовали "другие структуры данных", когда для этой цели создана встроенная структура - HashSet.

  • Это O (n). Вы, вероятно, не будете намного лучше, чем это, используя другие методы, если только вы не сделаете что-то действительно умное и не опуститесь до O (log n).
  • Это Java, а не C. Имеются легкодоступные структуры данных для этого безболезненно, без каких-либо дополнительных усилий для части программиста.

Из Java-документация по структуре коллекций:

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

Добавление

В большинстве комментариев ниже утверждается, что это всего лишь упражнение - определение навыков программиста. Мой контраргумент в этом прост:

Это "интервью" для позиции программирования Java. Java, будучи объектно-ориентированным языком, имеет возможность выполнять такие задачи, не требуя разработки процесса с нуля (например, на C и других языках низкого уровня). Кроме того, Java не самый лучший выбор, когда проблема с пространственной сложностью. Тем не менее, снова введите запись в мой список выше.

Ответ 4

Хорошо, вы сами даете ответ: линейное хеширование действительно существует. он имеет сложность o (1)/o (1) согласно http://cgi.di.uoa.gr/~ad/MDE515/e_ds_linearhashing.pdf так что вы будете извлекать элементы из массива один за другим, используя первые несколько в качестве памяти для хэш-карты.
но на самом деле, это структура данных, которую вы реализуете сами.

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

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

Ответ 5

Это не использует линейное хеширование, но работает быстрее, чем O (N 2):

  • Выберите небольшое число C и используйте алгоритм грубой силы, чтобы найти первый дубликат для первых элементов C массива. Очистите первые элементы C, если ничего не найдено.
  • Выполните оставшиеся шаги, когда первые N элементов пусты. Первоначально N = C. После каждой итерации N удваивается.
  • Последовательно добавьте числа из индексов N + 1.. 3 * N/2 в хэш-таблицу в элементах первого N массива. Используйте открытую адресацию. После перемещения всех элементов N/2 коэффициент хэш-нагрузки должен быть равен 1/2. Прозрачное пространство, занятое N/2 элементами, которые мы только что переместили. Для следующих элементов N/4 выполните поиск каждого из них в хэш-таблице (таблицах), построенных до сих пор, затем помещаем их в пространство, которое всегда вдвое больше числа элементов. Продолжайте это до тех пор, пока элементы массива N-C не будут хэшированы. Найдите остальные элементы C в хэш-таблицах и сравните их друг с другом.
  • Теперь у нас есть N элементов массива без дубликатов, занимающих пространство 2 * N. Повторите их на месте.
  • Последовательно искать все остальные элементы массива в этой хэш-таблице. Затем очистите эти 2 * N элементов, установите N = 2 * N и продолжим с шага 3.

Шаги 3..5 могут быть упрощены. Просто хэш-элементы N + 1.. 3 * N/2 и найдите все остальные элементы массива в этой хэш-таблице. Тогда сделайте то же самое для элементов 3 * N/2 + 1.. 2 * N. Это в два раза медленнее, чем исходный алгоритм, но в то же время O (N log N).

Другой альтернативой является использование первых N пустых элементов для построения двоичного дерева поиска для элементов N + 1.. 3 * N/2 и поиска всех остальных элементов массива в этом дереве. Тогда сделайте то же самое для элементов 3 * N/2 + 1.. 2 * N. (Это работает только в том случае, если массив достаточно мал, и его элементы могут быть проиндексированы целыми значениями).

Алгоритм, описанный выше, является вероятностным и в среднем работает в O (N log N) времени. Его наихудшая сложность - O (N 2). Альтернатива с бинарным деревом поиска может иметь O (N log 2 N) наихудшую сложность, если дерево самобалансируется. Но это сложно. Задачу можно выполнить в O (N log 2 N) наихудшем случае с более простым алгоритмом.

Этот алгоритм последовательно выполняет итерацию через массив и сохраняет следующий инвариант: наибольшая возможная подматрица с размером, которая имеет силу два, которая находится слева от текущей позиции, начинается с индекса 0 и сортируется; следующая такая подматрица следует за ним и также сортируется; и т.д. Другими словами, двоичное представление текущего индекса описывает, как много отсортированных подмассивов предшествует ему. Например, для индекса 87 (1010111) мы имеем один элемент в индексе 86, сортированную пару в индексе 84, отсортированную подматрицу из 4 элементов в 80, отсортированную подматрицу из 16 элементов в 64 и отсортированную sub-array из 64 элементов в начале массива.

  • Итерация через массив
  • Поиск текущего элемента во всех предыдущих под-массивах с использованием двоичного поиска.
  • Сортировка текущего элемента вместе с предшествующими подмассивами, которые соответствуют завершающим "единицам" в двоичном представлении текущего индекса. Например, для индекса 87 (1010111) нам нужно отсортировать текущий элемент вместе с тремя подмассивами (1 + 1 + 2 + 4 = 8 элементов). Этот шаг позволяет добавить текущий элемент в подматрицы, сохраняя инвариант алгоритма.
  • Продолжить следующую итерацию шага 1.

Ответ 6

Мне было представлено это дополнительное ограничение дополнительной памяти, только регистры. Вот что я придумал:

outer: for (i = 0; i < arr.length - 1; i++)
 for (j = i+1; j < arr.length; j++)
   if (arr[i] == arr[j])
     break outer;

Если я и j являются < arr.length, - это индексы первого двойного значения и соответствуют.

Это немного лучше, чем O (n ^ 2), так как j никогда не покрывает всю длину arr

Ответ 7

Псевдокод:

res = -1;
startArray = [...];
sortedArray = mergeSort(startArray);
for i = 1 to n
     x = bynary_search(sortedArray, startArray[i]); //array, element
     if ((sorted_array[x] == sortedArray[x-1])    ||   (sorted_array[x] == sortedArray[x+1]))
           res = i;
           break;
if (res != -1)
     print('First duplicate is ',startArray[res]);
else
     print('There are no duplicates');

Сбой сортировки наихудшего случая O (n log n)

Двоичный поиск в худшем случае O (log n)

n раз Бинарный поиск в худшем случае O (n log n)

Всего O (n log n)

Ответ 8

Здесь O (n) Время на среднем алгоритме

public static int firstRepeatingElement(int[] elements) {
    int index = -1;
    Set<Integer> set = new HashSet<Integer>();

    for (int i = elements.length - 1; i >=0; i--) {
        if (set.contains(elements[i])) {
            index = i;
        }
        set.add(elements[i]);
    }
    if (index != -1) {
        return elements[index];
    }
    throw new IllegalArgumentException("No repeating elements found");
}

Вот тестовые примеры

@Test
public void firstRepeatingElementTest() {
    int [] elements = {1,2,5,7,5,3,10,2};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}

@Test(expected=IllegalArgumentException.class)
public void firstRepeatingElementTestWithException() {
    int [] elements = {1,2,5,7,3,10};
    int element = ArrayUtils.firstRepeatingElement(elements);
    assertThat(element, is(2));
}