K-th Smallest (Quickselect)
JavaScript
Hard
4 views
Problem Description
Given an array and integer k, find the k-th smallest element (1-based) without fully sorting.
Input Format
Line1: n k. Line2: n integers.
Output Format
One integer answer.
Official Solution
const fs=require('fs');const a=fs.readFileSync(0,'utf8').trim().split(/\\s+/);if(!a[0])process.exit(0);let i=0;const n=Number(a[i++]);let k=Number(a[i++])-1;let arr=[];for(let j=0;j<n;j++)arr.push(Number(a[i++]));const swap=(x,y)=>{const t=arr[x];arr[x]=arr[y];arr[y]=t;};let l=0,r=n-1;while(l<=r){let pivot=arr[Math.floor((l+r)/2)];let p=l,q=r;while(p<=q){while(arr[p]<pivot)p++;while(arr[q]>pivot)q--;if(p<=q){swap(p,q);p++;q--;}}if(k<=q)r=q;else if(k>=p)l=p;else break;}process.stdout.write(String(arr[k]));
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!