Kth Smallest (Quickselect)

Kth Smallest (Quickselect)

Hard PHP PHP Arrays 30 views
Explanation Complexity

Problem Statement

Find the k-th smallest value in the array (1-based k).

Input Format

Line1 n k. Line2 n integers.

Output Format

One integer.

Example

7 3
7 2 5 3 1 6 4
3

Constraints

n

Input / Output Format

Input Format
Line1 n k. Line2 n integers.
Output Format
One integer.
Constraints
n

Examples

Input:
7 3 7 2 5 3 1 6 4
Output:
3

Example Solution (Public)

PHP 
<?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; }
}
?>

Official Solution Code

<?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; }
}
?>
Please login to submit solutions.
Editor
Output

                                        

                                    

                                    

                                        

                                                                                    
Please login to submit solutions.