编程之美2.5 寻找最大的K个数
来源：程序员人生 发布时间：2014-10-04 08:00:00 阅读次数：2805次
在一个数组中寻找最大的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);
}
}
}
}
生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
