<?php 
/**
 * 最小的K个数
 *
 * 输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
 *
 * 解法一
 * 可以改变数组的情况下
 * 使用快速排序
 * 解法二
 * 维护一个最大堆，在堆中存K个数（堆顶为最大当前K个数中的最大数），每个数与堆顶比较，当i个数小于堆顶元素，堆顶出堆，该第i个数入堆，最后堆中的元素为最小的k个数
 */


function GetLeastNumbers_Solution($array, $k)
{
    if (!is_array($array) || empty($array)) {
  		return null;
  	}
    $length = count($array);
  	$start = 0;
  	$end = $length - 1;
  	$index = Partition($array, $start, $end);
  	while ($index != $k) {
  		if ($index > $k) {
  			$end = $index - 1;
  			$index = Partition($array, $start, $end);
  		} else {
  			$start = $index + 1;
  			$index = Partition($array, $start, $end);
  		}
  	}
  	$result = array_slice($array, 0, $index);
    return $result;
}


function Partition(&$array, $start, $end)
{   
	$temp = $array[$start];
	while ($start < $end) {
		while (($start < $end) && ($array[$end] >= $temp)) {
			$end--;
		}
		$array[$start] = $array[$end];
		while (($start < $end) && ($array[$start] <= $temp)) {
			$start++;
		}
		$array[$end] = $array[$start];
	}
	$array[$start] = $temp;
    return $start;
}


$arr = [4,5,1,6,2,7,3,8];
var_dump(GetLeastNumbers_Solution($arr, 4));