Көптүктөр жана сөздүктөр: set жана map
set жана map: таандыктыкты тез текшерүү, ар түрдүүлөрдү жана жыштыктарды O(log n) убакытта эсептөө.
«Бул сан мурда кездешти беле» дегенди массивди кыдырып текшерүү — ар бир текшерүүгө O(n). set жана map структуралары муну O(log n) убакытта жасайт, анткени ичинде элементтерди тең салмактанган даракта сактайт.
• std::set — уникалдуу элементтердин көптүгү: insert, count, erase. Элементтерди иреттелген түрдө сактайт.
• std::map — «ачкыч → маани» сөздүгү: count[x]++ биринчи кайрылууда эле ачкычты нөл менен өзү түзөт.
Орточо O(1) убакыттагы хеш-версиялары да бар: unordered_set / unordered_map — тезирээк, бирок иреттелгендиги жок.
Классика: агымдын биринчи кайталанган элементин табуу.
Биринчи кайталануу. Киргизиңиз: 6, андан кийин 3 1 4 1 5 9
map жыштык анализи үчүн алмаштыргыс: бир өтүү менен ар бир сөз канча жолу кездешкенин эсептейбиз. map боюнча өтүү ачкычтарды иреттелген тартипте берет — көбүнчө бул кокустук эмес, пайдалануу керек болгон бонус.
Сөздөрдүн жыштыгы. Киргизиңиз: 5, андан кийин: apple banana apple cherry banana
Тандоо багыттары:
• иреттелгендик же «эң жакын элемент» керек — set/map;
• ылдамдык гана керек — unordered-версиялары;
• кайталанмалар керек — multiset.
Тапшырма: n сан берилген; так бир жолу кездешкендерин өсүү тартибинде чыгарыңыз (map муну алты сапта чечет).
Сабакты өттүм деп белгилеп, рекурсияга өтүңүз.