Najčešći broj
★☆☆ laganoKoji se broj u listi pojavljuje najviše puta? Ako ih je više, ispiši najmanji od njih.
- Ulaz
- U prvom retku N. U drugom retku N cijelih brojeva.
- Izlaz
- Najčešći broj.
- Ograničenja
- 1 ≤ N ≤ 100 000
Nema novog gradiva. Na jednom mjestu su svi pristupi iz cjeline i tragovi po kojima ih prepoznaješ, a zatim šest zadataka razine županijskog natjecanja.
| Lekcija | Ideja | Ključni zapis |
|---|---|---|
| 22 | simulacija: stanje, pravila, ponavljanje | varijable stanja + petlja |
| 23 | gruba sila (brute force): isprobaj sve | petlje po svim mogućnostima, j od i + 1 |
| 24 | rječnik, skup, n-torka | d[k] += 1 · s.add(x) · (kraj, pocetak) |
| 25 | složenost (time complexity) | O(N), O(N²), O(log N), skrivene petlje |
| 26 | prefiksni zbroj (prefix sum) | p[r] - p[l - 1] |
| 27 | binarno pretraživanje (binary search) | mid = (lo + hi) // 2 |
| 28 | pohlepni algoritam (greedy) | sortiraj, pa uzimaj najbolje |
Kad pročitaš zadatak, ovi tragovi često otkriju koji pristup treba:
| Trag u zadatku | Vjerojatan pristup |
|---|---|
| opisana su pravila koja se ponavljaju | simulacija |
| mali N (do 20, do 200) | gruba sila |
| „koliko puta se pojavljuje“, „različiti“, „je li već viđen“ | rječnik ili skup |
| mnogo pitanja o zbroju dijela niza | prefiksni zbroj |
| sortirani podaci, „najmanji koji…“, „najveći koji…“, ogroman N | binarno pretraživanje |
| „što više“, „što manje“, a podatke možemo poredati | pohlepno, uz provjeru |
Uvijek prvo pogledaj ograničenja i procijeni složenost, kao u lekciji 25. Rješenje koje je točno, ali presporo, evaluator ne prihvaća.
Prije zadataka provjeri jesi li razumio gradivo. Klikni na odgovor za koji misliš da je točan.
Ograničenje N ≤ 10^5. Koje je rješenje vjerojatno dobro?
N^2 bi bio 10^10 koraka.
Puno upita o zbroju dijela niza. Koji pristup?
Prefiksni zbroj daje odgovor u jednom koraku.
Traži se najmanji X za koji uvjet vrijedi, a uvjet „raste” s X. Koji pristup?
Monotoni uvjet: binarno pretraživanje.
Poredani su od lakšeg prema težem. Za svaki zadatak prvo odluči koji pristup treba, pa tek onda piši program.
Koji se broj u listi pojavljuje najviše puta? Ako ih je više, ispiši najmanji od njih.
Koliko je različitih riječi u tekstu?
Predmeti stižu na traku jedan za drugim, a znamo masu svakog. Pakiramo ih redom u kutije nosivosti C: predmet ide u trenutnu kutiju ako stane, a ako ne stane, zatvaramo kutiju i otvaramo novu. Koliko je kutija potrebno?
Simulacija: stanje je koliko je već u trenutnoj kutiji. U primjeru su kutije 4 + 5, zatim 3 + 7 i na kraju 2 + 6.
Koliko ima trojki brojeva iz liste (na različitim mjestima) čiji je zbroj 0?
N je mali, pa je dovoljna gruba sila sa tri petlje. Koliko je to trojki za N = 150?
Za N dana znamo količinu kiše. Q puta pitamo: kojeg je dana ukupna količina kiše od prvog dana prvi put dosegla barem X? Dani su numerirani od 1. Ako se to nikad ne dogodi, ispiši −1.
Prefiksni zbrojevi kiše nikad ne padaju, jer količina nije negativna. Zato na njima možeš binarno tražiti prvi dan s p[dan] ≥ X.
Na izletu je N učenika i znamo masu svakog. U kanu stanu najviše dva učenika, a njihova ukupna masa ne smije biti veća od W. Koliko najmanje kanua treba?
Sortiraj mase. Najteži učenik mora u neki kanu. Ako s njim stane najlakši, neka idu zajedno; ako ne stane, najteži ide sam. Pamti dva indeksa: najlakšeg i najtežeg koji još nisu raspoređeni.
Točno, ali presporo rješenje · pohlepno pravilo bez provjere · pomak indeksa za jedan u prefiksnim zbrojevima i binarnom pretraživanju