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

Question

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

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

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

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

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

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

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

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

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

Answer 1

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

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

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

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

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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 никогда не покрывают всю длину обр

Answer 5

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

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

От Java Documentation on the Collections Framework:

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

Добавление

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

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

Answer 6

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

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

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

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

Answer 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'); 

Merge рода худший случай O (N журнал п)

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

n раз Двоичный поиск в худшем случае О (п войти п)

Итого О (п войти п)

Answer 8

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

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)); 
}