文章目录1 题目2 解决方案2.1 思路2.3 时间复杂度2.4 空间复杂度3 源码1 题目题目前K大数Top k Largest Numbers描述在一个数组中找到前K大的数。lintcode题号——544难度——medium样例1输入: [3, 10, 1000, -99, 4, 100] 并且 k 3 输出: [1000, 100, 10]样例2输入: [8, 7, 6, 5, 4, 3, 2, 1] 并且 k 5 输出: [8, 7, 6, 5, 4]2 解决方案2.1 思路该题可以用quick select的算法来将小于k的数都移到左边再用quick sort快排进行排序。也可以考虑使用优先序列来做维护一个容量为k的优先序列需要取前k个数每次取完序列顶部再弹出进行k次即可。2.3 时间复杂度使用quick select的方式移动小于k的值到左边耗时O(n)对左边的k个数排序耗时O(k * log k)总时间复杂度为O(n k * log k)。使用优先序列的方式将元素放入序列耗时O(log k)需要进行n次将元素弹出序列耗时O(logk)需要进行k次总时间复杂度O(n * log k) O(k * log k) O(n * log k);在k趋近于n的时候两种排序方式的耗时相近。2.4 空间复杂度使用quick select的方式空间复杂度为O(1)。使用优先序列的方式需要一个容量为k的最小堆优先序列所以空间复杂度为O(k)。3 源码细节使用优先序列的方式建立一个最小堆优先序列每次弹出堆顶的最小元素保留k个较大的元素。因为是最小堆优先序列组装结果的时候需要按照弹出顺序的倒序来组装。C版本/** * param nums: an integer array * param k: An integer * return: the top k largest numbers in array */ vectorint topk(vectorint nums, int k) { // write your code here vectorint result; if (nums.size() k) { return result; } priority_queueint, vectorint, greaterint numQueue; // 最小堆优先序列 for (auto it : nums) { numQueue.push(it); if (numQueue.size() k) // 弹出多余的数 { numQueue.pop(); } } for (int i 0; i k; i) { result.insert(result.begin(), numQueue.top()); // 倒序组装结果 numQueue.pop(); } return result; }