剑指offer 面试题30：最小的K个数
题目： 输入n个整数，找出其中最小的k个数。例如：例如输入4 、5 、1、6、2、7、3 、8 这8 个数字，则最小的4 个数字是1 、2、3 、4
提交网址： http://www.nowcoder.com/practice/6a296eb82cf844ca8539b57c23e6e9bf?tpId=13&tqId=11182
分析：
想到3种方法，第1种是先快排，然后挑出其中的前k个，时间复杂度为O(n logn)；第2种方法是使用partition函数(进行一次快速排序用哨兵数分割数组中的数据)，时间复杂度：O(n)；第3种是小顶堆(优先队列)，时间复杂度：O(n logk). 第3种在海量计算中应用广泛...
STL中的优先队列默认是大顶堆，此题是生成一个小顶堆，即可解决...
堆排序
数据对象为：数组,链表，不稳定，时间复杂度为O(n logk)，空间复杂度为O(1)，(最大堆，有序区)从堆顶把根卸出来放在有序区之前，再恢复堆。
priority_queue调用 STL里面的 make_heap(), pop_heap(), push_heap() 算法实现，也算是堆的另外一种形式。
方法3 大顶二叉堆
AC代码：
-
#include<cstdio>
-
#include<vector>
-
#include<queue> // 用到其中的优先队列priority_queue
-
using namespace std;
-
class Solution {
-
public:
-
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
-
{
-
vector<int> res;
-
if(k<=0 || k>input.size()) return res;
-
priority_queue<int> q; // STL中的优先队列默认是大顶堆
-
unsigned int i=0;
-
while(i<input.size())
-
{
-
q.push(input[i]);
-
if(q.size()>k) q.pop();
-
i++;
-
}
-
while(!q.empty())
-
{
-
res.push_back(q.top()); // C语言中的top()可返回顶部元素的值，也可返回顶部元素的指针，程序员自行设计; C++的STL中top()返回的是顶部的值
-
q.pop();
-
}
-
return res;
-
}
-
};
-
// 以下为测试部分
-
int main()
-
{
-
Solution sol;
-
vector<int> vec1={2,5,3,7,9,8,6};
-
vector<int> vec2={5,7,6,9,11,10,8};
-
vector<int> vec3={7,4,6,5};
-
vector<int> res1=sol.GetLeastNumbers_Solution(vec1,3);
-
vector<int> res2=sol.GetLeastNumbers_Solution(vec2,5);
-
vector<int> res3=sol.GetLeastNumbers_Solution(vec3,2);
-
-
for(int i:res1)
-
printf("%d ", i);
-
printf("\n");
-
for(int i:res2)
-
printf("%d ", i);
-
printf("\n");
-
for(int i:res3)
-
printf("%d ", i);
-
printf("\n");
-
return 0;
-
}
priority_queue函数列表
| 函数 |
描述 |
| 构造析构 |
| priority_queue <Elem> c |
创建一个空的queue 。
注：priority_queue构造函数有7个版本，请查阅MSDN |
| 数据访问与增减 |
| c.top() |
返回队列头部数据 |
| c.push(elem) |
在队列尾部增加elem数据 |
| c.pop() |
队列头部数据出队 |
| 其它操作 |
| c.empty() |
判断队列是否为空 |
| c.size() |
返回队列中数据的个数 |
| |
可以看出priority_queue的函数列表与栈stack的函数列表是相同的。
方法2 Partition函数
AC代码：
-
#include<cstdio>
-
#include<vector>
-
using namespace std;
-
class Solution{
-
public:
-
int partion(vector<int> a,int len,int low,int high)
-
{
-
int base=a[low];
-
int i=low, j=high;
-
while(i != j)
-
{
-
while(i<j && a[j]>=base) j--;
-
while(i<j && a[i]<=base) i++;
-
if(i<j) // 交换
-
{
-
int temp=a[i];
-
a[i]=a[j];
-
a[j]=temp;
-
}
-
}
-
a[low]=a[i];
-
a[i]=base;
-
return i;
-
}
-
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
-
{
-
vector<int> res;
-
int len=input.size();
-
if(len<=0) return res;
-
int start=0;
-
int end=len-1;
-
int index=partion(input,len,start,end);
-
while(k-1 != index)
-
{
-
if(k-1 < index)
-
{
-
end=index-1;
-
index=partion(input,len,start,end);
-
}
-
else
-
{
-
start=index+1;
-
index=partion(input,len,start,end);
-
}
-
}
-
for(int i=0;i<k;i++)
-
res.push_back(input[i]);
-
return res;
-
}
-
};
-
// 以下为测试部分
-
int main()
-
{
-
Solution sol;
-
vector<int> vec1={2,5,3,7,9,8,6};
-
vector<int> vec2={5,7,6,9,11,10,8};
-
vector<int> vec3={7,4,6,5};
-
vector<int> res1=sol.GetLeastNumbers_Solution(vec1,3);
-
vector<int> res2=sol.GetLeastNumbers_Solution(vec2,5);
-
vector<int> res3=sol.GetLeastNumbers_Solution(vec3,2);
-
-
for(int &i:res1)
-
printf("%d ", i);
-
printf("\n");
-
for(int &i:res2)
-
printf("%d ", i);
-
printf("\n");
-
for(int &i:res3)
-
printf("%d ", i);
-
printf("\n");
-
return 0;
-
}
其实还有一种思路：
可以用较为hack的手段进行。比如要获得一个堆中的最小值：
-
priority_queue<int> pq;
-
pq.push( -1 * v1) ;
-
pq.push( -1 * v2) ;
-
pq.push( -1 * v3) ;
分别是插入v1, v2, v3变量的相反数，那么取相反数后的这些值变相构成为了最大堆，只是每次从pq取值后，要再次乘以-1即可获得堆中最小值...
相关链接：
编程之美之2.5 寻找最大的K个数 - Yoona http://blog.csdn.net/sunnyyoona/article/details/26380473
版权声明：本文为博主Bravo Yeung(知乎UserName同名)的原创文章，欲转载请先私信获博主允许，转载时请附上网址http://blog.csdn.net/lzuacm。 https://blog.csdn.net/yanglr2010/article/details/51318794
