如题:给定一个无序数组,如何查找第K小的值。...例子如下:
在一个无序数组,查找 k = 3 小的数
输入:arr[] = {7, 10, 4, 3, 20, 15} 输出:7
在一个无序数组,查找 k = 4 小的数
输入:arr[] = {7..., 10, 4, 3, 20, 15} 输出:10
几种思路如下和复杂度分析如下:
(1)最简单的思路直接使用快排,堆排或者归并排,排序之后取数组的k-1索引的值即可,时间复杂度为O(nLogn)
(2...注意,如果思路理解了,那么该题目的变形也比较容易处理,比如
(1)如给定一个无序数组,查找最小/大的k个数,或者叫前k小/大的所有数。...(2)给定一个大小为n数组,如果已知这个数组中,有一个数字的数量超过了一半,如何才能快速找到该数字?