Ալգորիթմներ և Տվյալների Կառուցվածքներ

Ցուցակի 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

Բացատրություն

  1. Տեսակավորված ցուցակը կլինի [-2, 3, 4, 6, 8, 10] ⇒ 3-րդ ամենափոքր տարրը 4 է

  2. Տեսակավորված ցուցակը կլինի [-4, -3, 0, 5, 7, 8, 10] ⇒ 2-րդ ամենափոքր տարրը -3 է

Հուշում 1

Օգտագործեք պատահական բաժանում (partitioning) QuickSort ալգորիթմի նմանությամբ։

տարրերի տեսակավորումը անիրագործելի է սահմանված ժամանակի սահմանափակման պայմաններում։

Հուշում 2

Դուք կարող եք զանգվածը բաժանել QuickSort-ի նմանությամբ, ընտրելով պատահական pivot։ Այնուհետև կարող եք պահել միայն ձեզ անհրաժեշտ մասը և անտեսել մյուս մասը։

Այս գործընթացը հնարավոր է կրկնել այնքան ժամանակ, մինչև անտեսված տարրերի քանակը ձեր ընթացիկ տարրից առաջ հավասարվել է k-ի։

Պատահական բաժանումը, իրականում, ունի սպասվող գծային ժամանակային բարդություն ։ Գիտե՞ք, թե ինչու։

Հուշում 3

Յուրաքանչյուր անգամ, երբ պատահականորեն բաժանում ենք զանգվածը, ստացվող զանգվածի ակնկալվող չափը դառնում է ընթացիկի կեսը։ Այսպիսով, եթե այս պահին զանգվածի չափը n է, ապա մեկ բաժանումից հետո կարող ենք դուրս նետել կեսը՝ n/2, երկու բաժանումից հետո՝ n/4, և այդպես շարունակ։ Այս շարքը գումարվում է որպես ։

Այդուհանդերձ, ալգորիթմը կարող էWorst-case(ամենավատ) տարբերակում ունենալ բարդություն, եթե պատահականորեն ընտրված տարրերը չբաժանեն զանգվածը ըստ սպասվող n/2 չափի:

Constraints

Time limit: 5 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue