Получить первый элемент больше заданного числа из отсортированного списка

Question

У меня есть два списка.Список B подобен базе данных, с которой мне нужно сравнивать каждый элемент списка A, один за другим.Допустим,

B = [0.6, 1.7, 3, 4.5]
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

B является отсортированным списком, поэтому для каждого A [i] всякий раз, когда алгоритм находит число, равное> = A [i] в ​​B, он должен возвращать его в качестве вывода.Поэтому мой вывод должен выглядеть примерно так:

C = [0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Не могли бы вы предложить мне самое простое решение, максимально избегая вложенных циклов?

Answer 1

Рекурсивный способ (разрушительный для исходных списков), работает также, если list_a содержит число больше, чем list_b :

def pick(lst, ref, res=None):
  if res == None: res = []
  if len(lst) == 0: return res
  if ref[0] >= lst[0]:
    res.append(ref[0])
    lst.pop(0)
  elif len(ref) == 1 and ref[0] < lst[0]:
    # res.extend(lst) # if want to append the rest of lst instead of stop the loop
    # or do whathever is best for you
    return res
  else: ref.pop(0)
  pick(lst, ref, res)
  return res


list_b = [0.6, 1.7, 3, 3.9]
list_bb = [0.5]
list_a = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

print(pick(list_a, list_b))
#=> [0.6, 1.7, 1.7, 1.7, 3, 3, 3]

print(pick(list_a, list_bb))
#=> []

Answer 2

Поскольку B отсортировано, вы можете использовать bisect для двоичного поиска правильного значения в B:

>>> B = [0.6, 1.7, 3, 4.5]
>>> A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]
>>> import bisect
>>> [B[bisect.bisect_left(B, a)] for a in A]
[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Это имеет сложность O(alogb), с a и b, то есть длины A и B соответственно.Предполагая, что A также отсортирован, как в вашем примере, вы также можете сделать это в O(a+b):

i, C = 0, []
for a in A:
    while B[i] < a:
        i += 1
    C.append(B[i])

Обратите внимание, однако, что оба подхода (а также другие ответы, опубликованные до сих пор)) завершится ошибкой, если A содержит число больше, чем любое число в B.

Answer 3

Только next будет делать (, если я вас правильно понял ):

A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]
B = [0.6, 1.7, 3, 4.5]

C = [next(b for b in B if b >= a) for a in A]

print(C)  # -> [0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Answer 4

Если вы можете использовать стороннюю библиотеку, одним из решений будет NumPy через np.searchsorted:

import numpy as np

B = np.array([0.6, 1.7, 3, 4.5])
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

res = B[np.searchsorted(B, A)]

array([ 0.6,  1.7,  1.7,  1.7,  3. ,  3. ,  3. ,  4.5,  4.5])

Это будет более эффективно, чем последовательный цикл или алгоритм, основанный наbisect из стандартной библиотеки.

Answer 5

Поскольку ваш заданный список B отсортирован, вы можете использовать:

B = [0.6, 1.7, 3, 4.5]
A = [0.6, 0.9, 1.2, 1.5, 2, 2.5, 3, 4, 4.5]

def first_greater_elem(lst, elem):
    for item in lst:
       if item >= elem:
         return item

Тогда просто используйте понимание списка .

C = [first_greater_elem(B,item) for item in A ]

Output

[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]

Другим подходом может быть использование метода bisect_left из пакета bisect.

C = [B[bisect_left(B,item)] for item in A ]

Вывод

[0.6, 1.7, 1.7, 1.7, 3, 3, 3, 4.5, 4.5]