Блог

Я студент-информатик, и это мой первый курс! Итак, я вижу, что это должно быть очень просто, но почему-то я просто не могу уловить это в своей голове.

Так что — упражняйтесь сами:

Def получает два массива с действительными числами (int) и некоторыми S (int). Нужно найти X (некоторый int из массива 1) Y (int из массива 2) = S. НО сложность должна быть O(n m), где n и m-длины массивов.

 def finding_sum(arr1, arr2, s):
  for i in arr1:
    if (s-i in arr2):
      return i, s-i
 

Я думал об этом — но В модуле это все равно, что пройти через весь массив, и это O(n*m).

Преобразуйте второй список в набор. Преобразование равно O(m) ,а поиск набора равен O(1).

 def finding_sum(arr1, arr2, s):
    set2 = set(arr2)
    for i in arr1:
        if s-i in set2:
            return i, s-i
 

Вы можете создать вспомогательную структуру данных:

 def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    for n in arr2:
        if n in lookup:
            return s-n, n
 

Набор lookup занимает линейное время для создания и обеспечивает O(1) проверку содержимого. Вы можете сократить это, используя next :

 def finding_sum(arr1, arr2, s):
    lookup = {s-n for n in arr1}
    return next((s-n, n) for n in arr2 if n in lookup)
 

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

 def finding_sum(arr1, arr2, s):
    return next((s-n, n) for n in set(arr2).intersection(map(s.__sub__, arr1)))