Kth Smallest (Quickselect)
PHP
Hard
5 views
Problem Description
Find the k-th smallest value in the array (1-based k).
Input Format
Line1 n k. Line2 n integers.
Output Format
One integer.
Official Solution
<?php
$inputText=trim(stream_get_contents(STDIN));
if($inputText==='') exit;
$tokens=preg_split('/\\s+/', $inputText);
$idx=0; $n=intval($tokens[$idx++] ?? 0);
$k=intval($tokens[$idx++] ?? 1)-1;
$a=[];
for($i=0;$i<$n;$i++) $a[] = intval($tokens[$idx++] ?? 0);
$lo=0; $hi=$n-1;
while(true){
$pivot=$a[intdiv($lo+$hi,2)];
$i=$lo; $j=$hi;
while($i<=$j){
while($a[$i]<$pivot) $i++;
while($a[$j]>$pivot) $j--;
if($i<=$j){ $t=$a[$i]; $a[$i]=$a[$j]; $a[$j]=$t; $i++; $j--; }
}
if($k<=$j) $hi=$j;
elseif($k>=$i) $lo=$i;
else{ echo $a[$k]; break; }
}
?>
Solutions (0)
No solutions submitted yet. Be the first!
No comments yet. Start the discussion!