Kth Smallest Quickselect
Medium
Programming Interview
Algorithms
16 views
Problem Statement
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.
Example
6 3 7 10 4 3 20 15
7
Constraints
1
Input / Output Format
Input Format
First line n k. Second line n integers.
Output Format
One integer kth.
Constraints
1
Examples
Input:
6 3
7 10 4 3 20 15
Output:
7
Example Solution (Public)
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]))
Official Solution Code
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]))
Please login to submit solutions.