欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

求无序数组中第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);

 

相关标签: 第k大的数