你必须设计并实现时间复杂度为

}在这个代码中我们首先创建一个优先队列pq。

然后我们遍历数组nums对于每个元素我们将其添加到队列中。

如果队列的大小大于k我们就删除队列中的最小元素。

最后我们返回队列的头部元素这就是第k个最大的元素。

log

k)因为我们需要对每个元素进行堆操作堆操作的时间复杂度是O(log

k)。

虽然题目要求时间复杂度为O(n)但是这个算法在实际中的性能已经非常好了因为log

方法二快速选择

n){swap(nums,p,i);p;}}swap(nums,p,right);return

p;}public

getIndex(nums,left,right);if(index

k){return

quickSelect(nums,index1,right,k);}else{return

quickSelect(nums,left,index-1,k);}}public

int

quickSelect(nums,0,nums.length-1,nums.length

k);}

}快速选择是快速排序的一个优化它在平均情况下的时间复杂度是O(n)。

在这个代码中我们首先使用快速选择算法来找到第k个最大的元素。

快速选择算法的基本思想是我们选择一个枢轴元素然后将数组分为两部分一部分是小于枢轴的元素另一部分是大于枢轴的元素。

然后我们根据k和枢轴的位置决定是在左边的部分还是右边的部分继续查找。

如果k等于枢轴的位置那么枢轴就是我们要找的元素。