Как найти минимальный элемент из двух массивов в данной временной сложности в питоне

Question

У меня есть 2 массивов А и Б. Я пытаюсь найти минимум из элементов, которые являются общими в массивах А и В.

Нравится, если A = [1,3,2,1] & B = [4,2,5,3,2], поэтому он должен возвращать 2, потому что это минимальный элемент, который входит как в A & B. Мой код ниже работает для этого случая, но в некоторых случаях он не работает. Я не знаю, как это исправить. Пожалуйста помоги!

def findMin(A, B): 
    A.sort() 
    B.sort() 
    i = 0 
    for x in A: 
     if i < len(B) - 1 and B[i] < x: 
      i += 1 
     if x == B[i]: 
      return x 
    return -1 

Кроме того, я хочу наихудший время сложность быть O((N+M)*log(N+M))

Answer 1

Itertools цепь Подход:

>>> import itertools 
>>> A = [1,3,2,1] 
>>> B = [4,2,5,3,2] 
>>> min(x for x in itertools.chain(A, B) if x in A and x in B) 
2 

Answer 2

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

shared = (set(a).intersection(b)) 

shared = sorted(shared) 
print shared[0] 

Возвращает 3

Answer 3

я предлагаю использовать set сек потому что это будет намного быстрее из-за его реализация. Вам просто нужно использовать функцию min над пересечением двух списков, преобразованных в set. Это слишком просто, удобно и не требует сортировки.

min(set(A) & set(B)) 

Чтобы получить первоначальный алгоритм работы вам нужно просто заменить первый if по while цикла:

while i < len(B) - 1 and B[i] < x: 

Answer 4

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

>>> A = [1,3,2,1] 
>>> B = [4,2,5,3,2] 
>>> min(set(A).intersection(B)) 
2 

что бы сделать вашу функцию:

def findMin(A, B, default=-1): 
    return min(set(A).intersection(B), default=default) 

Аргумент по умолчанию - это то, что возвращается, если между двумя списками нет пересечения (кажется, вы выбрали -1), но это дополнение Python 3.x, если вы застряли с Python 2.x , вам нужно потенциально обрабатывать его с помощью исключений, например:

def findMin(A, B, default=-1): 
    try: 
     return min(set(A).intersection(B)) 
    except ValueError: 
     return default 

Как сложности, его худший случай O(len(A) * len(B)) для пересечения, хотя средний случай O(min(len(A), len(B)) (см time complexity), то min операции вам нужно добавить сверху O(N).

Answer 5

В случае, если есть большая разница в размерах массивов быстрый способ заключается в создании set из меньшего для intersection:

def find(a, b): 
    small, large = sorted([a, b], key=len) 
    return min(set(small).intersection(large), default=-1) 

Сравнение с 100000 и 10000 элементы:

import random 
import timeit 

def find_no_sort(a, b): 
    return min(set(a).intersection(b), default=-1) 

a = [random.randrange(0, 100000) for _ in range(100000)] 
random.shuffle(a) 
b = [random.randrange(0, 100000) for _ in range(10000)] 
random.shuffle(b) 

print('Sorted: ', timeit.timeit('find(a, b)', number=100, globals=globals())) 
print('Not sorted: ', timeit.timeit('find_no_sort(a, b)', number=100, globals=globals())) 

Выход (Python 3.5.1 в Windows 8):

Sorted: 0.8935029393830678 
Not sorted: 1.7727491360998975