python birden çok listeden en küçük aralık

Question

Her listeden en az bir öğe kullanarak bir grup tamsayı listesinden en küçük aralığı bulmalıyım. Bu değerler, üç listelerinden 391, 395 ve 398 kapsar, çünkü, [398 391]

list1=[228, 240, 254, 301, 391] 
list2=[212, 345, 395] 
list3=[15, 84, 93, 103, 216, 398, 407, 488] 

Bu örnekte en küçük aralık olacaktır.

Her listesinde en az bir değere sahip olacak ve aralığı en hızlı hesaplama yolu ne olurdu daha birçok listeleri

olabilir?

Answer 1

Giriş listeleriniz sıralandığından, birleştirme sıralama kullanabilirsiniz ve yalnızca birleştirilen bir sonraki değer, sondan farklı bir listeden geldiğinde bir aralığı sınamanız gerekir. Listelerin her birinde gördüğünüz son değeri takip edin ve en düşük değer ile akım arasındaki aralıkları hesaplayın. Bu, N'un tüm giriş listelerinin toplam öğe sayısı olduğu O(N) doğrusal zaman yaklaşımıdır.

yaklaşım aşağıdaki uygular:

def smallest_range(*lists): 
    iterables = [iter(it) for it in lists] 
    iterable_map = {} 
    for key, it in enumerate(iterables): 
     try: 
      iterable_map[key] = [next(it), key, it] 
     except StopIteration: 
      # empty list, won't be able to find a range 
      return None 
    lastvalues, lastkey = {}, None 
    candidate, candidatediff = None, float('inf') 

    while iterable_map: 
     # get the next value in the merge sort 
     value, key, it = min(iterable_map.values()) 
     lastvalues[key] = value 

     if len(lastvalues) == len(lists) and lastkey != key: 
      minv = min(lastvalues.values()) 
      difference = value - minv 
      if candidatediff > difference: 
       candidate, candidatediff = (minv, value), difference 
     lastkey = key 

     try: 
      iterable_map[key][0] = next(it) 
     except StopIteration: 
      # this iterable is empty, remove it from consideration 
      del iterable_map[key] 

    return candidate 

Demo: listeleri birçok/büyük olsun ama listeleri ön ayrımı olan girişi üstlenmez gibi bu çözüm önemli ölçüde yavaşlatır

>>> list1 = [228, 240, 254, 301, 391] 
>>> list2 = [212, 345, 395] 
>>> list3 = [15, 84, 93, 103, 216, 398, 407, 488] 
>>> smallest_range(list1, list2, list3) 
(391, 398) 

Answer 2

:

from itertools import product 

def smallest_range(*arrays): 

    result = min((sorted(numbers) for numbers in product(*arrays)), key=lambda n: abs(n[0] - n[-1])) 

    return (result[0], result[-1]) 

list1 = [228, 240, 254, 301, 391] 
list2 = [212, 345, 395] 
list3 = [15, 84, 93, 103, 216, 398, 407, 488] 

print(smallest_range(list1, list2, list3)) 

KULLANIMI:

list1 = [228, 240, 254, 301, 391] 
list2 = [212, 345, 395] 
list3 = [15, 84, 93, 103, 216, 398, 407, 488] 

print(smallest_range(list1, list2, list3)) 

BASKI:

(391, 398)