Найдите максимальный элемент, который является общим в двух массивах?

Учитывая два массива, как найти максимальный элемент, который является общим для обоих массивов?

Я думал о сортировке массивов (n log n), а затем выполнить бинарный поиск каждого элемента из одного отсортированного массива (начиная с более крупного) в другом массиве до тех пор, пока не будет найдено совпадение.

например:

a = [1,2,5,4,3]
b = [9,8,3]

Maximum common element in these array is 3

Можем ли мы лучше, чем n log n?

Ответы

Ответ 1

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

Ответ 2

Вы можете использовать O(N) пространство.
Просто пройдите первый массив и поместите все элементы в HashTable. Это O(N)
Затем пройдите второй массив, отслеживая текущий максимум и проверяя, находится ли элемент в HashTable. Это также O(N). Таким образом, общая продолжительность работы O(N) и O(N) дополнительное пространство для HashTable

Пример в Java:

public static int getMaxCommon(int[] a, int[] b){  
  Set<Integer> firstArray = new HashSet<Integer>(Arrays.asList(a));  
  int currentMax = Integer.MIN_VALUE;  
  for(Integer n:b){  
     if(firstArray.contains(n)){  
         if(currentMax < n){  
              currentMax = n  
         }
     }   
  }   
  return currentMax;  
}

Ответ 3

Хотя это зависит от сложности времени различных операций на определенных языках, как насчет создания наборов из массивов и нахождения максимального значения в пересечении двух наборов? Исходя из сложностей времени для операций на Python, в среднем для O (n) для заданных назначений O (n) для пересечений было бы O (n) и O (n) для нахождения максимального значения. Таким образом, средний случай был бы O (n).

Однако! Наихудший случай был бы O (len (a) * len (b)) → O (n ^ 2) из-за худшей временной сложности множества пересечений.

Подробнее здесь, если вам интересно: http://wiki.python.org/moin/TimeComplexity

Ответ 4

Если вы уже знаете диапазон чисел, который будет в ваших массивах, вы можете выполнить сортировку, а затем выполнить бинарный поиск, как вы хотели. Это приведет к времени выполнения O (n).

Ответ 5

псевдокод:

sort list1 in descending order
sort list2 in descending order
item *p1 = list1
item *p2 = list2
while ((*p1 != *p2) && (haven't hit the end of either list))
  if (*p1 > *p2)
    ++p1;
  else
    ++p2;
// here, either we have *p1 == *p2, or we hit the end of one of the lists
if (*p1 == *p2)
  return *p1;
return NOT_FOUND;

Ответ 6

Не идеальное, но простое решение, O (len (array1) + len (array2))

import sys


def find_max_in_common(array1, array2):
    array1 = set(array1)
    array2 = set(array2)

    item_lookup = {}

    for item in array1:
        item_lookup[item] = True

    max_item = -sys.maxsize

    intersection = False

    for item in array2:
        if not item_lookup.get(item, None):
            continue
        else:
            intersection = True
            if item > max_item:
                max_item = item

    return None if not intersection else max_item