5. 微软面试题： 查寻最小的k个元素（数组）

5. 微软面试题： 查找最小的k个元素（数组）

题目：输入n个整数，输出其中最小的k个。

例如输入7,2,4,5,1,3,6,8这8个数字，则最小的4个数字为1，2，3和4。

下面使用快速排序和分治法的思想，

1）先找选一个元素a遍历一次剩余的其他元素，使得a左边的元素都是小于它的，a右边的元素都是大于它的。

2）再统计a 左边的元素或者包括a 与 k的关系，等于的话，就直接输出，大于，那就在左边里面继续1），小于的话，那就在右边里面继续查找k-左边元素的个数-1个最小的整数。

看实现（写的很烂，今儿一点感觉都没有，以后再修正！）

#include <iostream>
#include<vector>
using namespace std;

//使用快速排序的思想，查找最小的k个数
void findmink(int* data, int i, int j, int k, vector<int>& res)
{
	//使用一次快速排序步骤 
	int ii = i+1;
	int jj = j-1;
	int pos = i;
	while(ii <= jj)
	{
		while(ii <= jj && data[jj] > data[pos]) 
			jj --;
		if(ii <= jj)
		{
			int tmp = data[pos];
			data[pos] = data[jj];
			data[jj] = tmp;
			pos = jj;
			jj --;
		}
		while(ii <= jj && data[ii] < data[pos])
			ii ++;
		if(ii <= jj)
		{
			int tmp = data[pos];
			data[pos] = data[ii];
			data[ii] = tmp;
			pos = ii;
			ii --;
		}
	}
	

	if(pos-i+1 == k)
	{//OK
		for(ii=i; ii <= pos; ii++)
			res.push_back(data[ii]);
	}
	else if(pos-i == k)
	{
		for(ii=i; ii < pos; ii++)
			res.push_back(data[ii]);
	}
	else if( pos-i+1 < k)
	{
		for(ii=i; ii <= pos; ii++)
			res.push_back(data[ii]);
		findmink(data, pos +1 , j, k-pos +i -1, res);
	}
	else
	{
		findmink(data, i, pos, k, res);
	}
	 
}

int main()
{
	int array[8] = {7,2,4,5,1,3,6,8};
	vector<int> mink;
	findmink(array, 0, 8, 4, mink);
	int i = 0;
	while(i<mink.size())
	{
		cout << mink[i++] << ",";
	}
	return 0;
}

输出结果为：

1,2,3,4