(Алгоритм) Найти, если два несортированных массива имеют какие-либо общие элементы за O (n) времени без сортировки?

Question

У нас есть два несортированных массива, и каждый массив имеет длину n.Эти массивы содержат случайные целые числа в диапазоне 0-n ¹⁰⁰ .Как определить, имеют ли эти два массива какие-либо общие элементы в O (n) / линейном времени?Сортировка не допускается.

Answer 1

Hashtable спасет вас.Действительно, это как швейцарский нож для алгоритмов.
Просто вставьте в него все значения из первого массива и затем проверьте, присутствует ли какое-либо значение из второго массива.

Answer 2

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

Эскиз доказательства: Каждое число на входе принимает O (log (n ^ 100)) = O (100 log n) = O (log n) битов.Таким образом, весь ввод O (n log n) битов, которые не могут быть прочитаны за O (n) времени.Следовательно, любой алгоритм O (n) не может прочитать весь ввод и, следовательно, не реагировать, если эти биты имеют значение.

Answer 3

Тест на линейность

Использование хеш-функции Mathematica и целых чисел произвольной длины.

Проверяется до n = 2 ^ 20 , генерируя случайные числа до (2 ^ 20) ^ 100 = (приблизительно 10 ^ 602)

На всякий случай ... программа:

k = {};
For[t = 1, t < 21, t++,
  i = 2^t;
  Clear[a, b];
  Table[a[RandomInteger[i^100]] = 1, {i}];
  b = Table[RandomInteger[i^100], {i}];
  Contains = False;
  AppendTo[k,
   {i, First@Timing@For[j = 2, j <= i, j++,
       Contains = Contains || (NumericQ[a[b[[j]]]]);
       ]}]];
ListLinePlot[k, PlotRange -> All, AxesLabel -> {"n", "Time(secs)"}]

Answer 4

Отвечая на вопрос Нейла: Поскольку в начале вы знаете, какой у вас N (два массива размера N), вы можете создать хеш с размером массива 2 * N * some_ratio (например: some_ratio = 1.5). При таком размере почти все простые хеш-функции обеспечат вам хорошее распространение сущностей.

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

Answer 5

Поместите элементы первого массива в хеш-таблицу и проверьте наличие, просматривая второй массив. Это дает вам решение в O (N) среднем случае.

Если вы хотите действительно O (N) решение для наихудшего случая, тогда вместо использования хеш-таблицы используйте линейный массив в диапазоне 0-n ^ 100. Обратите внимание, что вам нужно использовать только один бит на запись.

Answer 6

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

Define largeArray(n)
// First pass
for(element i in firstArray)
   largeArray[i] = true;

// Second pass
Define hasFound = false;
for(element i in secondArray)
   if(largeArray[i] == true) 
      hasFound = true;
      break;

Answer 7

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

Вот реализация на языке Perl.

#!/usr/bin/perl
use strict;
use warnings;
sub find_common_elements{ # function that prints common elements in two unsorted array
my (@arr1,@array2)=@_; # array elements assumed to be filled and passed as function arguments 

my $hash; # hash map to store value of one array

# runtime to prepare hash map is O(n). 
foreach my $ele ($arr1){
$hash->{$ele}=true; # true here element exists key is integer number and value is true,          duplicate elements will be overwritten

# size of array will fit in memory as duplicate integers are ignored   ( mx size will     be 2 ^( 32) -1 or 2^(64) -1 based on operating system) which can be stored in RAM.
} 
# O(n ) to traverse second array and finding common elements in two array
foreach my $ele2($arr2){
  # search in hash map is O(1), if all integers of array are same then hash map will have         only one entry and still search tim is O(1) 
   if( defined $hash->{$ele}){  
   print "\n $ele is common in both array \n";
   }
  }
 } 

Надеюсь, это поможет.

Answer 8

Вы пробовали счетную сортировку ? Он прост в реализации, использует пространство O (n), а также имеет \ theta (n) временную сложность.