Kth Smallest Quickselect
Programming Interview
Medium
6 views
Problem Description
You're given {x}. Compute kth smallest element using quickselect style and output it.
Input Format
First line n k. Second line n integers.
Output Format
One integer kth.
Sample Test Case
Input:
6 3
7 10 4 3 20 15
Official Solution
import sys,random
p=sys.stdin.read().strip().split()
if len(p)<2: sys.exit(0)
n=int(p[0]); k=int(p[1])
a=list(map(int,p[2:2+n]))
k-=1
l=0
r=n-1
while l<=r:
pivot=a[random.randint(l,r)]
i=l
j=r
while i<=j:
while a[i]<pivot:
i+=1
while a[j]>pivot:
j-=1
if i<=j:
a[i],a[j]=a[j],a[i]
i+=1
j-=1
if k<=j:
r=j
elif k>=i:
l=i
else:
break
sys.stdout.write(str(sorted(a[l:r+1])[k-l] if l<=k<=r else a[k]))
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!