Puteți utiliza statistici ordinale.
Am împărțit recursiv subarray în două părți. Luăm din subarraje un element de susținere (pivot) și împărțim subarrayul cu mai mult decât elementul de susținere și mai puțin. Dacă acelea care sunt mai mult decât necesare, procesează recursiv partea dreaptă, dacă mai puțin - stânga, dacă este atât de multe - răspunsul este găsit.
Algoritmul de împărțire (partiție) este același cu cel utilizat în sortarea rapidă (rapidsort), diferența fiind că doar o ramură este împărțită.
Cel mai bun și mediu este O (n), cel mai rău fiind O (n ^ 2),
Metodele de tratament sunt aceleași ca și în cazul rapidului - alegerea corectă a pivotului. Puteți alege aleatoriu.
A se vedea, de asemenea: k-t statistici ordinale, mediană.
Algoritmul în sine este numit rapidselect.
răspuns primit 10 noiembrie '16 la 9:54
Am luat această decizie:
Dacă trebuie să obțineți n numere maxime, atunci vom crea o coadă. Apoi mergem prin colecție, dacă dimensiunea coada este mai mică decât numărul specificat, atunci pur și simplu adăugați elementul curent acolo. În caz contrar, comparați cu elementul minim din coadă. Dacă elementul curent este mai mare, ștergeți minimul și adăugați unul nou.
Postat pe Nov 10 '16 la 9:10 am
a dat seama, aici, poate cineva și ajutor))
răspunsul este 24 noiembrie 16 la 12:42
ce ar trebui să fie sortat steagul? are întotdeauna o valoare adevărată, dar nu este verificată nicăieri - Grundy 24 Nov '16 la 12:45
Folosiți mai bine sortarea standard decât cârjele dvs. :) - gil9red pe 24 noiembrie '16 la 12:58
Articole similare
Trimiteți-le prietenilor: