Comment puis-je réduire le nombre de boucles ou de complexité

Question

Donc, ce que j'essaie de faire est de trouver le nombre de nombres alternés de telle sorte qu'il alterne avec -ve et signe positif pour par exemple: 1 -2 3 -4 m'obtiendrait 4 3 2 1 de 1 à -4 y compris les deux nombres il y a 4 nombres. Simillarly pour 1 1 -3 2 me donnerait 1 3 2 1 Maintenant j'ai le code mais je ne peux pas l'optimiser et il me renvoie une erreur de limite de temps dépassée même si cela fonctionne pour un flux d'entrée modéré.

j=0 
count=0 
length=(raw_input()) 
st=map(int,raw_input().split()) 
while j+1 < len(st): 
    k=j+1 
    count=0 
    temp=j 
    while k<len(st) and ((st[k]<0 and st[j]>0) or (st[k]>0 and st[j]<0)): 
     count+=1 
     k+=1 
     j+=1 
    print count+1, 
    j=temp+1 
print 1 

Answer 1

Essayez d'utiliser des boucles au lieu de while que vous évite des affectations de variables:

st = map(int, raw_input().split()) 
length = len(st)-1 
for i in range(length): 
    count = 1 
    for j in range(i, length): 
     if (st[j]<0 and st[j+1]>0) or (st[j+1]<0 and st[j]>0): 
      count += 1 
     else: 
      break 
    print(count) 
print(1) 

Cela donnera:

<< 1 -2 3 4 
>> 4 
>> 3 
>> 2 
>> 1 

<< 1 1 -3 2 
>> 1 
>> 3 
>> 2 
>> 1 

Il peut aussi être un peu plus rapide si vous extraire les numéros de la liste une fois au lieu de deux fois:

st = map(int, raw_input().split()) 
length = len(st)-1 
for i in range(length): 
    count = 1 
    for j in range(i, length): 
     first, second = st[j:j+2] 
     if (first<0 and second>0) or (first>0 and second<0): 
      count += 1 
     else: 
      break 
    print(count) 
print(1) 

La dernière chose que je voudrais essayer est de vérifier qu'ils sigs sont différents avec un seul comparisson mais je ne pense pas vraiment que ce soit plus rapide:

st = map(int, raw_input().split()) 
length = len(st)-1 
for i in range(length): 
    count = 1 
    for j in range(i, length): 
     product = st[j] * st[j+1] 
     if product != abs(product): 
      count += 1 
     else: 
      break 
    print(count) 
print(1)