Блог

Главная - Вопросы по программированию - Пересечение 2 массивов, O(n), на месте, только постоянный объем дополнительной памяти

Пересечение 2 массивов, O(n), на месте, только постоянный объем дополнительной памяти

#algorithm #time-complexity

Вопрос:

Заданы 2 целых массива, A и B(целые числа могут быть отрицательными). Цель состоит в том, чтобы найти пересечение этих массивов, результат должен храниться в одном из исходных массивов и не должен содержать повторяющихся элементов. Может использоваться только постоянный объем памяти.

Комментарии:

1. Если вы не совершите некоторые махинации (что очень возможно, вы можете) с тем фактом, что элементы являются гарантированными целыми числами, что выводит вас из алгебраической модели — этого нельзя сделать, так как это позволит вам легко решить проблему различимости элементов в линейное время в алгебраической модели. (tl;dr: если это возможно, вы каким-то образом должны использовать тот факт, что элементы являются целыми числами)

2. Единственный способ сделать это в O(n), который я вижу, — это сделать мой «постоянный объем памяти» равным int.MaxVal/4 (или проще 2*Int.MaxVal 1 ). Тогда все довольно просто. И да, это будет использовать тот факт, что элементы являются целыми числами.

3. Имеют ли целые числа какие-либо минимальные/максимальные ограничения?

Ответ №1:

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

Псевдокод:

 FindCommons(A, B):
  IntegersSort(A)
  IntegersSort(B)
  i = j = 0
  out = 0
  while (i < length(A) amp;amp; j < length(B)):
    if A[i] == B[j]:
      A[out  ] = A[i]
      i  
      j  
    else if A[i] < B[j]:
      i  
    else:
      j  
  // Output is A in range (0, out) once this is completed.

Ответ №2:

Использование наборов в python, если числа уникальны

Метки: , , ,