Por ejemplo, si la lista es: [2,1,2,5,7,6,9] hay 3 formas posibles de dividir:
[2,1,2] [5,7,6,9]
[2,1,2,5] [7,6,9]
[2,1,2,5,7,6] [9]
Se supone que debo calcular cuántas veces se puede dividir la lista de manera que cada elemento de la izquierda sea más pequeño que cada elemento de la derecha. Entonces, con esta lista, la salida sería 3.
Aquí está mi solución actual:
def count(t): c= 0 for i in range(len(t)): try: if max(t[:i]) < min(t[i:]): c+=1 except: continue return cEl código anterior hace lo correcto, pero no tiene una complejidad de tiempo O(n). ¿Cómo podría lograr el mismo resultado, pero más rápido?
Calcule todos los máximos de prefijos y mínimos de sufijos en tiempo lineal. Y combinarlos en tiempo lineal.
from itertools import accumulate as acc from operator import lt def count(t): return sum(map(lt, acc(t, max), [*acc(t[:0:-1], min)][::-1]))Jacques solicitó un punto de referencia:
1444.6 ms Jacques_Gaudin 5.0 ms Kelly_Bundy 1424.5 ms Jacques_Gaudin 4.4 ms Kelly_Bundy 1418.2 ms Jacques_Gaudin 4.7 ms Kelly_BundyCódigo ( ¡Pruébelo en línea! ):
from timeit import timeit from itertools import accumulate as acc from operator import lt def Kelly_Bundy(t): return sum(map(lt, acc(t, max), [*acc(t[:0:-1], min)][::-1])) def Jacques_Gaudin(t): if not t: return 0 v, left_max = list(t), max(t) c, right_min = 0, left_max while (item := v.pop()) and v: if item == left_max: left_max = max(v) if item < right_min: right_min = item if left_max < right_min: c += 1 return c funcs = [ Jacques_Gaudin, Kelly_Bundy, ] t = list(range(12345)) for func in funcs * 3: time = timeit(lambda: func(t), number=1) print('%6.1f ms ' % (time * 1e3), func.__name__)Mi respuesta resultó ser muy similar a la de Kelly anterior: ambos calculamos los mínimos y máximos para puntos de división válidos y luego verificamos la condición en cada división.
Soy alrededor de un 50% más lento que el de Kelly, ya que no es completamente funcional como el de Kelly.
from itertools import accumulate as acc from typing import List def paddy3118(lst: List[int]) -> int: # min of RHS for any split min_from_r = list(acc(lst[::-1], min))[::-1] # max of LHS for any split max_from_l = list(acc(lst, max)) # Condition for valid split return sum(max_from_l[split] < min_from_r[split+1] for split in range(len(lst) - 1)) La siguiente función puede generar datos de prueba interesantes (pruebe count == swap para argumentos de count más grandes):
def _gen_swap(count, swaps): ans = list(range(count)) for i in range(swaps): s = random.randint(0, count - 2) ans[s], ans[s+1] = ans[s+1], ans[s] return ansmi intento:
def count(t): max_el = t[0] min_el = min(t[1:]) res = 0 for i in range(len(t)-1): if t[i] == min_el: min_el = min(t[i+1:]) if max_el < t[i]: max_el = t[i] if max_el < min_el: res +=1 return resBastante sencillo, solo calcule el máximo/mínimo si pudiera ser diferente.