Različiti
★☆☆ laganoKoliko je različitih brojeva u listi?
- Ulaz
- U prvom retku N. U drugom retku N cijelih brojeva.
- Izlaz
- Broj različitih brojeva.
- Ograničenja
- 1 ≤ N ≤ 100 000
Tko je pobijedio na izborima? Koliko je različitih brojeva u listi? Kako složiti rang listu? Uz liste, Python ima još tri spremnika koja to čine lakim.
Na izborima za predsjednika razreda svaki učenik napiše jedno ime. Kako prebrojati glasove za svakog kandidata? Za to služi rječnik (engl. dictionary, u Pythonu dict). Rječnik pamti parove: ključ i njegovu vrijednost, kao imenik u kojem uz svako ime piše broj.
glasovi = {"Ana": 3, "Ivo": 5}
print(glasovi["Ana"])
glasovi["Ana"] += 1
glasovi["Marko"] = 1
print(glasovi)
print(len(glasovi))| Zapis | Što radi |
|---|---|
{} | prazan rječnik |
d["Ana"] | vrijednost uz ključ "Ana" |
d["Marko"] = 1 | dodaje novi par ili mijenja postojeću vrijednost |
"Ana" in d | postoji li ključ "Ana" |
len(d) | broj parova |
d.values() | sve vrijednosti (npr. max(d.values()) je najveća vrijednost) |
Čitanje ključa koji ne postoji javlja grešku KeyError. Prije čitanja provjeri s in.
Najčešća upotreba rječnika: koliko puta se svaka vrijednost pojavila. Za svaku novu vrijednost provjerimo je li već u rječniku. Ako jest, povećamo brojač; ako nije, dodamo je s brojem 1.
Kroz rječnik prolazimo petljom po ključevima. sorted(d) daje ključeve poredane po abecedi.
glasovi = {"Ivo": 2, "Ana": 3, "Marko": 1}
for ime in sorted(glasovi):
print(ime, glasovi[ime])Skup (engl. set) pamti vrijednosti bez ponavljanja i bez redoslijeda. Ako dodamo nešto što već postoji, skup se ne mijenja.
s = set() s.add(5) s.add(3) s.add(5) print(len(s)) print(3 in s) print(len(set([4, 1, 4, 4, 2, 1])))
len(set(lista)) je broj različitih elemenata liste. U lekciji 19 smo to radili sortiranjem; ovo je kraće.
x in lista provjerava element po element, kao kad tražiš ime u neporedanom popisu. Za listu od 100 000 elemenata to je 100 000 usporedbi. x in skup i x in rjecnik odgovore gotovo odmah, bez obzira na veličinu.
| Provjera | Lista od 100 000 | Skup od 100 000 |
|---|---|---|
x in ... | do 100 000 koraka | otprilike 1 korak |
| 100 000 takvih provjera | do 10 milijardi koraka: presporo | oko 100 000 koraka: brzo |
Zato zadatak „Prvi ponovljeni“ iz lekcije 17 za velike ulaze rješavamo skupom umjesto liste:
vidjeni = set() for x in map(int, input().split()): if x in vidjeni: print(x) break vidjeni.add(x)
Ovdje nam treba samo prvi ponovljeni broj, pa nakon njega break iz lekcije 8 prekida petlju.
Ponekad nekoliko vrijednosti uvijek ide zajedno: koordinate (x, y), bodovi i ime, sat i minuta. Za to služi uređena n-torka (engl. tuple): nekoliko vrijednosti u okruglim zagradama. Dvije vrijednosti čine par, tri trojku.
tocka = (3, 5) print(tocka[0]) print(tocka[1]) x, y = tocka print(x + y)
N-torka se ne može mijenjati, kao ni string: tocka[0] = 7 javlja grešku. Ako trebaš drugu vrijednost, napraviš novu n-torku.
Raspakiravanje x, y = tocka već znaš iz recepta a, b = map(...). Isti trik zamijeni dvije varijable u jednom retku, bez treće varijable iz lekcije 2:
a = 5 b = 9 a, b = b, a print(a, b)
Lista ne može biti ključ rječnika ni element skupa, ali n-torka može. Tako lako pamtimo polja na ploči. Robot iz lekcije 22: na koliko je različitih polja stao, uključujući početno?
x = 0 y = 0 posjeceno = set() posjeceno.add((x, y)) for n in input(): if n == "R": x += 1 elif n == "L": x -= 1 elif n == "U": y += 1 else: y -= 1 posjeceno.add((x, y)) print(len(posjeceno))
Robot je bio na (0, 0), (1, 0), (1, 1), (0, 1) i opet (0, 0). Skup pamti svako polje samo jednom, pa je odgovor 4.
Lista n-torki sortira se po prvom elementu, a kad su prvi jednaki, po drugom, i tako dalje. To je točno ono što treba za rang listu.
rezultati = [(85, "Marko"), (92, "Ivo"), (85, "Ana")] rezultati.sort() print(rezultati)
Na rang listi želimo više bodova prvo, a kod jednakih bodova ime po abecedi. Trik: spremimo negativne bodove. Tada sortiranje od manjeg prema većem stavlja najviše bodova na početak, a imena ostaju po abecedi.
rezultati = [(-85, "Marko"), (-92, "Ivo"), (-85, "Ana")] rezultati.sort() for bodovi, ime in rezultati: print(ime, -bodovi)
Petlja for bodovi, ime in rezultati: raspakira svaku n-torku u dvije varijable.
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Brojimo pojave u rječniku d. Što napraviti s riječju w koje još nema u d?
Ako ključa nema, d[w] += 1 javlja grešku; zato je prvi put dodamo s vrijednošću 1.
Koliko je len(set([1, 2, 2, 3, 3, 3]))?
Skup sadrži samo različite vrijednosti.
Zašto je x in skup brže nego x in lista?
Skup i rječnik nalaze element odmah, bez prolaska kroz sve.
Koliko je različitih brojeva u listi?
Svaki učenik napisao je ime jednog kandidata. Tko je pobijedio i s koliko glasova? Ako više kandidata ima najviše glasova, pobjeđuje onaj koji je prvi po abecedi.
Prebroji glasove rječnikom. Zatim prođi ključevima poredanim po abecedi i traži najveći broj. Uvjet mora biti >, a ne >=, da kod jednakih ostane onaj koji je prvi po abecedi.
Brojevi stižu jedan po jedan. Koji je prvi broj koji se pojavio drugi put? Ako se nijedan ne ponavlja, ispiši 0.
Isti zadatak kao u lekciji 17, ali sada N može biti 100 000. S listom bi rješenje bilo presporo; upotrijebi skup.
Robot kreće s polja (0, 0) i izvrši niz naredbi R, L, U i D. Na koliko je različitih polja stao, uključujući početno?
Ispiši rang listu natjecanja: više bodova prvo, a kod jednakog broja bodova imena po abecedi.
Spremi svakog natjecatelja kao par (−bodovi, ime) i sortiraj listu parova, kao u dijelu 7.
Postoje li u listi dva broja (na različitim mjestima) čiji je zbroj točno K?
DA ili NE.Svi parovi iz lekcije 23 su presporo za 100 000 brojeva. Za svaki broj x zapitaj se: jesam li već vidio broj K − x? Brojeve koje si vidio pamti u skupu.
d[kljuc] = vrijednost.s.add(x), len(s).in je u skupu i rječniku gotovo trenutan, a u listi spor.(85, "Ana") drži vrijednosti koje idu zajedno; ne mijenja se, može biti ključ i element skupa.Čitanje ključa koji ne postoji (KeyError) · lista umjesto skupa za velike ulaze · zaboravljen uvjet za izjednačene rezultate