To sumproblemer i Python
Løsning av to sumproblemer i Python
Din tilnærming til dette emnet vil bli bestemt av ditt kompetansenivå. En metode er å sløyfe gjennom listen, sammenligne hvert element med resten. Vi går gjennom to forskjellige teknikker du kan bruke til å avhjelpe dette problemet.
Problemstilling: Returner alle par med to tall hvis sum tilsvarer et gitt mål fra en rekke heltall. Du kan anta at hver inngang har bare ett rasjonelt svar og at det samme elementet ikke kan brukes på nytt.
La oss starte med å forklare problemstatningen og deretter gå videre til mulige løsninger. Dette betyr virkelig at vi må konstruere en funksjon for å sjekke om det er noen verdier i denne matrisen som legger opp til det oppgitte målnummeret. Vi vil gi et grunnleggende eksempel for å beskrive problemet og løsningen.
Anta at vi fikk tallene [4, 6, 1, -5, 8], og målsummen var 9. Vi vil se om denne matrisen har et par tall som legger til den medfølgende målsummen. Som du ser, bør prosedyren returnere 8 og 1, som sum opp til 9 som ønsket total. Så hva er den beste strategien for å håndtere dette problemet? Se følgende seksjoner:
Løsning 1:
Det første svaret som kommer til tankene er å gjenta sløyfen to ganger. Den opprinnelige teknikken bruker to for løkker og reiser over hele matrisen to ganger for å nå den tiltenkte summen.
Så vi ville gå gjennom matrisen om gangen. På denne måten må du sjekke resten av matrisen for å vite om summen tilsvarer tallverdien som er spesifisert mens du går gjennom alle tallene.
For eksempel kan vi fortsette med 4 og jobbe oss gjennom resten av tallene [6, 1, -5, 8] for å avgjøre om å legge til 4 til noen av dem gir 9 eller ikke. Vi flytter til neste nummer, 6, og sjekker tallene på samme måte [1, -5, 8] for å se om å legge til nummer 6 til et av tallene som presenteres i matrisen gir 9, før vi fortsetter prosessen gjennom matrisen. Python -koden for et to -sum -problem med to for løkker vises nedenfor.
Def TwosumProb (my_arr, t_sum):for jeg i rekkevidde (len (my_arr) -1):
for j i rekkevidde (i, len (my_arr)):
Hvis my_arr [i]+my_arr [j] == t_sum:
Returner (my_arr [i]. my_arr [j])
komme tilbake[]
Tanken er å få frem at mens du gjør det kanskje ikke er den mest effektive bruken av tid. Det er fremdeles et levedyktig alternativ. To for Loop vil resultere i O (N2) tidskompleksitet siden du reiser to ganger å bruke to til loop vil bety å krysse N2 -tid når det gjelder tidskompleksitet. Fordi vi ikke lagrer noen heltall, er romkompleksiteten O (1).
Den andre løsningen er en sorteringsmetode. Selv om metoden kan ta mer plass, er den mer effektiv uten tvil.
Løsning 2:
Vi vil bruke sorteringsalgoritmen på denne måten siden sortering krever NLOG (N) tidstrinn, som er betydelig mer effektiv enn O (N2), ansatt i den forrige strategien med to for løkker.
Arrayens tall blir sortert først i denne tilnærmingen. Vi har to tips, den ene til venstre ved det første nummeret i matrisen og den andre til høyre ved siste nummer i matrisen.
Vi forenkler dette problemet igjen ved å bruke det tidligere array -eksemplet på [4, 6, 1, -5, 8]. Dataene blir deretter sortert for å gjenspeile et sortert utvalg av [-5, 1, 4, 6, 8]. Vår venstre peker (indikert som L_Pointer) vil bli satt til -5 og vår høyre peker (indikert som R_Pointer) til 8. Vi får se om -5 + 8 tilsvarer 9, som er den spesifiserte totalen. Nei, fordi 3 er mindre enn den oppgitte summen av 9. Vi skal flytte markøren vår i stigende rekkefølge, fra venstre til høyre.
Nå går vi tilbake til 1 og ser om tillegg av 1 og 8 tilsvarer 9, som det gjør. Dette gir oss paret vi leter etter. Parringene 1 og 8 vil nå bli skrevet ut som par som vil gi de nødvendige to numeriske summer.
La oss snakke om dette problemet litt mer. Tenk på følgende scenario: Hvis målsummen er ti og summen av en og åtte er mindre enn ti, vil venstre pekeren bli flyttet opp til fire i stigende rekkefølge. Totalt 4 og 8 tilsvarer 12, noe som er større enn målet totalt.
Som et resultat vil vi skifte riktig peker i synkende rekkefølge fra høyre posisjon til venstre. Den venstre pekeren er nå på 4, mens høyre peker har flyttet til 6. I denne situasjonen har vi nådd det nødvendige paret på 4 og 6, noe som vil gi oss det nødvendige beløpet på 10. Følgende Python -kode viser hvordan den forrige informasjonen implementeres nedenfor:
Def TwosumProb (my_arr, t_sum):my_arr.sortere()
L_Pointer = 0
r_pointer = len (my_arr) -1
Mens L_Pointer < r_pointer:
c_sum = my_arr [l_pointer]+my_arr [r_pointer]
Hvis c_sum == t_sum:
return (my_arr [l_pointer], my_arr [r_pointer])
elif c_sum
ellers:
r_pointer- = 1
komme tilbake[]
Vi bruker O (nlogn) når det gjelder tidskompleksitet på grunn av sortering, noe som er bedre enn den forrige løsningens metode, og det er litt dyrere fordi den bruker O (NLogn).
Konklusjon:
I denne artikkelen undersøkte vi det velkjente Python Two Sum-problemet og tilbød to levedyktige løsninger for deg å vurdere. Vi har lagt til to løsninger for å fikse dette to sumproblemet i Python. Disse eksemplene kan brukes på forskjellige måter i henhold til brukerens behov. Vi håper du fant artikkelen nyttig. Sjekk ut andre Linux -hint -artikler for flere tips og informasjon.