Zadali ste množinu intervalov ako {2,7}, {3,8}, {9,11}, {-4, -1} atď. Otázkou je nájsť k "tretinu z týchto množín intervalov.
Tiež duplikáty sa počítajú dvakrát. Napríklad, ak sú intervaly {1,4} a {2,6} a k = 3, potom je odpoveď 2, pretože ak intervaly vyrovnáme a zoradíme ich, spojíme ich, dostaneme postupnosť
1,2,2,3,3,4,4,5,6
Kde 3. min je 3.
Tento problém môže byť vyriešený mnohými spôsobmi. Snažím sa však nájsť ten, ktorý má minimálnu zložitosť času a priestoru.
odpovede:
3 pre odpoveď č. 1- Vyrovnajte intervaly.
- Zoraďte sploštenú postupnosť.
- Iterujte cez zoradenú sekvenciu, kým nenájdete
k-th element, pričom ignoruje duplicitné hodnoty.
Teraz urobme nejakú analýzu, kde sme sa rozhodli N celkový počet prítomných vo vašich intervaloch a M priemerný počet duplicitných hodnôt, ktoré bude mať číslo (bude 1 pre jedinečnú sploštenú sekvenciu).
Vesmírna zložitosť:
O (N)
kde by ste mohli urobiť lepšie, ak máte veľa duplicitných prvkov, iteráciou cez sploštenú sekvenciu, zatiaľ čo duplikované prvky sa zahodia.
Časová zložitosť:
O (k * M + NlogN)
- Sploštenie zaberá O (N)
- Zoradenie trvá O (NlogN)
- Iterácia trvá O (k * M)