面试题30
题目描述：
输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。
输入：
每个测试案例包括2行：
第一行为2个整数n，k(1<=n，k<=200000)，表示数组的长度。
第二行包含n个整数，表示这n个数，数组中的数的范围是[0,1000 000 000]。
输出：
对应每个测试案例，输出最小的k个数，并按从小到大顺序打印。
样例输入：
8 4 4 5 1 6 2 7 3 8
样例输出：
1 2 3 4
第一眼想法：排序（快排O（n*logn），但效率不高；因为空间复杂度最差情况为O（n)
正解：利用优先队列（默认有限队列priority_queue<int>为从大到小排序，priority_queue<int，vector<int>, greater<int> ?>为从大到小排序 ）。那么每次将数据插入到队列中，直到
队列中数据个数大于K个。由于采用默认值。因此每次队首的数据是最大的，每次使用改值与输入数据进行比较就可以了。然后再用一个栈，按照题目要求格式输出。这样时间复杂度为O（n*logk）
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
const int MAX = 35;
int num[MAX], pos[MAX], str[MAX];
int main(){
//priority_queue<int, vector<int>, greater<int> > Q;
priority_queue<int> Q;
int n, k, num;
while (scanf( "%d%d", &n, &k ) != EOF ){
while (!Q.empty()){
Q.pop();
}
for (int i = 0; i < n; ++i){
//cin >> num;
scanf("%d", &num);
if ( Q.size() < k){
Q.push(num);
}
else if (Q.size() == k && num < Q.top()){
Q.push(num);
}
if (Q.size() > k){
Q.pop();
}
}
stack<int>P;
while (!Q.empty()){
P.push(Q.top());
Q.pop();
}
if (!P.empty()){
//cout << P.top();
printf("%d", P.top());
P.pop();
}
while (!P.empty()){
//cout << " " << P.top();
printf(" %d", P.top());
P.pop();
}
printf("\n");
}
return 0;
}
如果说上面那样说二者的效果不够明显。那么下面这题和上面类似。
但由于求得是两数组中任意二者的和再排序。根据数据范围，则实际的数据量N == n*n；如果仍然按照快排去做的话。则会TLE。
题目链接
Problem Description
还记得Gardon给小希布置的那个作业么？（上次比赛的1005）其实小希已经找回了原来的那张数表，现在她想确认一下她的答案是否正确，但是整个的答案是很庞大的表，小希只想让你把答案中最大的M个数告诉她就可以了。
给定一个包含N(N<=3000)个正整数的序列，每个数不超过5000，对它们两两相加得到的N*(N-1)/2个和，求出其中前M大的数(M<=1000)并按从大到小的顺序排列。
Input
输入可能包含多组数据，其中每组数据包括两行：
第一行两个数N和M，
第二行N个数，表示该序列。
Output
对于输入的每组数据，输出M个数，表示结果。输出应当按照从大到小的顺序排列。
Sample Input
Sample Output
#include<iostream>
#include<cstring>
#include<cstdio>
#include<string>
#include<queue>
#include<algorithm>
#include<functional>
#include<stack>
using namespace std;
const int MAX = 3005;
int num[MAX * MAX];
int main(){
int n, m;
priority_queue<int, vector<int>, greater<int> > Q;
while (cin >> n >> m){
for (int i = 1; i <= n; ++i){
cin >> num[i];
}
while (!Q.empty())
Q.pop();
for (int i = 1; i <= n; ++i){
for (int j = i + 1; j <= n; ++j){
if ( Q.size() < m ){
Q.push(num[i] + num[j]);
}
else if ( Q.size() == m){
Q.push(num[i] + num[j]);
}
if (Q.size() > m){
Q.pop();
}
}
}
stack<int> P;
while (!Q.empty()){
P.push( Q.top() );
Q.pop();
}
cout << P.top();
P.pop();
while (!P.empty()){
cout << " " << P.top();
P.pop();
}
cout << endl;
}
return 0;
}