求无序数组中第k大的数
程序员文章站
2024-03-15 22:30:48
...
如果是排好序的数组,则比较简单,直接$arr[$k-1]就能求出,如果不是排好序的就需要先排序,但这种时间复杂度为O(n2),所以不能直接排序。我们知道快速排序就是找一个哨兵,使左边的数比它大,右边的数比它小,然后在对左右两边的数重复上次的动作。可以利用快速排序中的步骤,找的哨兵,在排完一步的序后,如果等于$k,则这个位置就是要找的,如果小于哨兵的位置,则重新对哨兵左边的数进行排序就好,没必要在对哨兵右边的数进行排序,因为要找的是第k大的数,比k小的数就不关心了。
用代码来实现以下:
//快速排序
function findPos(&$arr,$left,$right){
if ($left>$right) {
return false;
}
$target = $arr[$left];//哨兵
while ($left<$right) {
while ($left<$right && $arr[$right]<$target) {//从右边开始找一个比哨兵大的数,没有就往前挪
$right--;
}
$arr[$left] = $arr[$right];//找到了就和前边的数换位置
while ($left<$right && $arr[$left]>$target) {
$left++;
}
$arr[$right] = $arr[$left];
}
$arr[$right] = $target;
return $right;
}
function quickSort(&$arr,$left,$right,$k){
$pos = findPos($arr,$left,$right);//返回哨兵位置
if ($pos==$k) {
return $arr[$k];
}
if ($left<$pos && $k>$left && $k<$pos) {
return quickSort($arr,$left,$pos-1,$k);
}
if ($pos<$right && $k>$pos && $k<$right) {
return quickSort($arr,$pos+1,$right,$k);
}
}
$arr = [12,56,98,32,16,34,2,9,1];
$len = count($arr);
$res = quickSort($arr,0,$len-1,2);
var_dump($res);
上一篇: 【左神算法】数组实现队列