вопрос по поиску значения в массиве

Question

я видел несколько дней назад такую ​​проблему

there is given two array find      elements which are common   of these array

одним из решений была сортировка большого массива с последующим использованием бинарного алгоритма поиска
, а также есть еще один алгоритм - алгоритм грубой силы

 for (int i=0;i<array1.length;i++){
  for (int j=0;j<array2.length;j++){
 if (array1[i]==array2[j]){
//code here
}
}

это сложность O (array1.length array2.length);и мне интересно, сложность первого метода тоже такая же да?потому что мы должны сначала отсортировать массив, а затем использовать метод поиска. Сложность алгоритма двоичного поиска составляет log_2 (n), поэтому это означает, что общее время будет array.length log_2 (n) и как насчет сортировки?пожалуйста, объясните мне, что лучше

Answer 1

An O(M log N) решение

Пусть длина arr1 будет O(M), а длина arr2 будет O(N). Алгоритм сортировки / двоичного поиска: O(M log N).

Псевдокод выглядит следующим образом:

SORT(arr2)   # N log N

FOR EACH element x OF arr1             # M
   IF binarySearch(x, arr2) is FOUND   # log N
       DECLARE DUP x

O(M log N) значительно лучше, чем O(MN).

---

Линейно-временное решение

Существует также третий способ, который является O(M+N), с использованием набора, который имеет вставку и тест O(1). Набор на основе хеша соответствует этому ожиданию.

Псевдокод выглядит следующим образом:

INIT arr1set AS emptySet

FOR EACH element x OF arr1    # M
   INSERT x INTO arr1set      # 1

FOR EACH element x OF arr2    # N
   IF arr1set CONTAINS x      # 1
      DECLARE DUP x

Answer 2

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

Answer 3

Сложность первого решения составит:

sort_complexity(longer_array) + smaller_array.length*log_2(longer_array.length)

Answer 4

Первый способ лучше. Если вы сортируете array1, сложность первого метода составляет O(array1.length*log(array1.length) + array2.length*log(array1.length)), потому что сначала вы сортируете первый массив (в O(array1.length*log(array1.length))), а затем для каждого элемента во втором массиве вы выполняете двоичный поиск в первом массиве. (в O(array2.length*log(array1.length)).