Altă 'soluţie':job_detail/369661?action=view-source care sortează elementele în ordine crescătoare şi are complexitatea <tex>O(Nlog_{2}N)</tex> ar trebui să obţină $50$ puncte.
*Marius* Un radix sort cât să ia? Grupezi câte 2^16. Are O(N + K).

*Mishu* O(N+K)? Nu iese O(N)? adica sortez şirul si afişez elementul $K$

O altă 'soluţie':job_detail/369662?action=view-source, cu complexitatea <tex>O(Nlog_{2}K)</tex>, care foloseşte un heap pentru a menţine cele mai mici $K$ elemente ar trebui să obţină $70$ puncte.
*Marus* Se poate mai bine de O(N logK). Poţi crea un min-heap în O(N) din care extragi K elemente. Deci O(N + KlogK) cât să ia?

*Mishu* Nu am înţeles exact cum zici. Dacă îmi creez un min-heap cu N elemente si extrag primele K nu iese O(NlogN + KlogN)?

În final, 'soluţia':job_detail/369692?action=view-source care ar trebui să obţină $100$ de puncte foloseşte funcţia de partiţionare a quicksort-ului pentru a determina a $K$-a statistică de ordine. Practic, acest algoritm este foarte asemănător quicksort-ului, doar că în loc să se sorteze tot şirul se vor sorta doar anumite porţiuni care ajută la determinarea soluţiei. Acest algoritm este implementat şi în STL, funcţia 'nth_element':http://cplusplus.com/reference/algorithm/nth_element/ găsindu-se în headerul 'algorithm':http://cplusplus.com/reference/algorithm/. O sursă demonstrativă se găseşte 'aici':job_detail/369659?action=view-source. Complexitatea acestui algoritm este în medie <tex>O(N)</tex>, însă teoretic în cel mai defavorabil caz poate atinge <tex>O(N^2)</tex> pentru că am putea fi extrem de nenorocoşi să partiţionăm în jurul celui mai mare element rămas. Dar deoarece algoritmul este aleator, nu există date de intrare particulare care să provoace comportamentul celui mai defavorabil caz.