Ցուցակի k-րդ ամենափոքր տարրը
Ձեզ տրված է
n ամբողջ թիվ և մի թիվ k. Պահանջվում է գտնել ցուցակի k-րդ ամենափոքր տարրը։ Երաշխավորված է, որ զանգվածի տարրերը բոլորն իրարից տարբեր են:Մուտք
Մուտքի առաջին տողում տրված են երկու ամբողջ թիվ
n և k (1 ≤ k ≤ n ≤ ):Հաջորդ տողում տրված են
n ամբողջ թվեր ( ), որոնք առանձնացված են բացատներով:Ելք
Ծրագիրը ելքում պետք է տպի տրված ցուցակի
k-րդ ամենափոքր տարրի արժեքը:Օրինակներ
Մուտք | Ելք |
6 3
10 -2 4 8 3 6 | 4 |
7 2
-4 5 8 -3 10 0 7 | -3 |
Բացատրություն
- Տեսակավորված ցուցակը կլինի [-2, 3, 4, 6, 8, 10] ⇒ 3-րդ ամենափոքր տարրը 4 է
- Տեսակավորված ցուցակը կլինի [-4, -3, 0, 5, 7, 8, 10] ⇒ 2-րդ ամենափոքր տարրը -3 է
Հուշում 1
Օգտագործեք պատահական բաժանում (partitioning) QuickSort ալգորիթմի նմանությամբ։
10^6 տարրերի տեսակավորումը անիրագործելի է սահմանված ժամանակի սահմանափակման պայմաններում։
Հուշում 2
Դուք կարող եք զանգվածը բաժանել QuickSort-ի նմանությամբ, ընտրելով պատահական pivot։ Այնուհետև կարող եք պահել միայն ձեզ անհրաժեշտ մասը և անտեսել մյուս մասը։
Այս գործընթացը հնարավոր է կրկնել այնքան ժամանակ, մինչև անտեսված տարրերի քանակը ձեր ընթացիկ տարրից առաջ հավասարվել է
k-ի։Պատահական բաժանումը, իրականում, ունի սպասվող գծային ժամանակային բարդություն ։ Գիտե՞ք, թե ինչու։
Հուշում 3
Յուրաքանչյուր անգամ, երբ պատահականորեն բաժանում ենք զանգվածը, ստացվող զանգվածի ակնկալվող չափը դառնում է ընթացիկի կեսը։ Այսպիսով, եթե այս պահին զանգվածի չափը
n է, ապա մեկ բաժանումից հետո կարող ենք դուրս նետել կեսը՝ n/2, երկու բաժանումից հետո՝ n/4, և այդպես շարունակ։ Այս շարքը գումարվում է որպես ։Այդուհանդերձ, ալգորիթմը կարող էWorst-case(ամենավատ) տարբերակում ունենալ բարդություն, եթե պատահականորեն ընտրված տարրերը չբաժանեն զանգվածը ըստ սպասվող
n/2 չափի:Constraints
Time limit: 2.5 seconds
Memory limit: 512 MB
Output limit: 1 MB