面试题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。

题目链接

#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;
}