首页 > 代码库 > 编程之美2.5 寻找最大的K个数

编程之美2.5 寻找最大的K个数

      在一个数组中寻找最大的K个数,我们首先说一种非常简单的方法,利用快速排序中的分割算法,即我们经常看见的partition。这个函数会返回一个 int 类型的值,这个值代表的是前一半数字和后一半数字的分割点,前一半数字都小于等于后一半数字(递增排序),所以,我们只要找到相对应的分割点,即可以找到最大的K个数,或者最小的K个数,这就是利用线性方法可以完成任务的方法。

      首先,给出函数声明:

int DutPartition(int*, int, int);
void DutFindMaxKInArray_1(int*, int, int);

源代码如下:

/*经典的快排分割程序*/
int DutPartition(int* A, int low, int high)
{
	/*哨兵,这里其实也可以用rand生成一个随机值,避免效率最低化*/
	int pivot = A[low];

	while (low < high)
	{
		while (low < high && A[high] >= pivot)
			--high;
		A[low] = A[high];

		while (low < high && A[low] <= pivot)
			++low;
		A[high] = A[low];
	}

	A[low] = pivot;
	/*最终返回“中点”位置*/
	return low;
}

/*这里的解法很简单,就是一直寻找index的最终位置,找到了就可以跳出循环了*/
void DutFindMaxKInArray_1(int* A, int size, int k)
{
	if (!A || size <= 0 || k < 1 || size < k)
		return;

	int index = DutPartition(A, 0, size - 1);

	/*寻找最终位置*/
	while (index != size - k)
	{
		if (index < size - k)
			index = DutPartition(A, index + 1, size - 1);
		else
			index = DutPartition(A, 0, index - 1);
	}
	
	/*输出最大的K个值*/
	for (int i = size - k; i < size; ++i)
		cout << A[i] << " ";
	cout << endl;
}

经过分析代码,我们可以知道,这个方法会改变原来数组中数字的顺序。假如说,不允许改变原来的结构呢?那么,我们可以利用最小堆解决TOPK的问题,最小堆的性质是堆顶元素是堆中元素值最小的一个,所以,我们只要判断下当前的堆顶元素是否比数组中元素小就可以了,如果是小,那么替换并重新调整堆,如果是大,那么不用理会这个元素。

      由于 stl 中 multiset 是利用红黑树实现的,可以实现堆的性质,所以,我们可以利用 multiset 来解决这个问题,这种方法得到的时间复杂度是O(nlogn)

      函数声明如下:

/*2.5 寻找最大的K个数*/
typedef std :: multiset<int, std :: less<int>>					intSet;
typedef std :: multiset<int, std :: less<int>> :: iterator		setInterator;
void DutFindMaxKInArray_2(const std :: vector<int>&, intSet&, int);

源代码如下:

/*第一种解法不好的地方在于它改变了数组中原来数的顺序*/
/*
 *第二种解法利用最小堆的思想寻找TOPK,是经典的大数据解题方法,
 *网络上很多类似的解释,这里,不做过多的解释
 */
void DutFindMaxKInArray_2(const std :: vector<int>& data, /*模拟最小堆*/intSet& leastNums, int k)
{
	leastNums.clear();

	if (k < 1 || data.size() < k)
		return;

	vector<int> :: const_iterator iter = data.begin();
	for (; iter != data.end(); ++iter)
	{
		if (leastNums.size() < k)
		{
			leastNums.insert(*iter);
		}
		else
		{
			setInterator it = leastNums.begin();

			if (*iter > *it)
			{
				leastNums.erase(it);
				leastNums.insert(*iter);
			}
		}
	}
}


编程之美2.5 寻找最大的K个数