編程之美2.5 尋找最大的K個數(shù)
來源：程序員人生 發(fā)布時間：2014-10-04 08:00:00 閱讀次數(shù)：2959次
在一個數(shù)組中尋找最大的K個數(shù)，我們首先說一種非常簡單的方法，利用快速排序中的分割算法，即我們經(jīng)常看見的partition。這個函數(shù)會返回一個 int 類型的值，這個值代表的是前一半數(shù)字和后一半數(shù)字的分割點，前一半數(shù)字都小于等于后一半數(shù)字（遞增排序），所以，我們只要找到相對應的分割點，即可以找到最大的K個數(shù)，或者最小的K個數(shù)，這就是利用線性方法可以完成任務的方法。
首先，給出函數(shù)聲明：
int DutPartition(int*, int, int);
void DutFindMaxKInArray_1(int*, int, int);
源代碼如下：
/*經(jīng)典的快排分割程序*/
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的最終位置，找到了就可以跳出循環(huán)了*/
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;
}
經(jīng)過分析代碼，我們可以知道，這個方法會改變原來數(shù)組中數(shù)字的順序。假如說，不允許改變原來的結構呢？那么，我們可以利用最小堆解決TOPK的問題，最小堆的性質是堆頂元素是堆中元素值最小的一個，所以，我們只要判斷下當前的堆頂元素是否比數(shù)組中元素小就可以了，如果是小，那么替換并重新調整堆，如果是大，那么不用理會這個元素。
由于 stl 中 multiset 是利用紅黑樹實現(xiàn)的，可以實現(xiàn)堆的性質，所以，我們可以利用 multiset 來解決這個問題，這種方法得到的時間復雜度是O(nlogn)
函數(shù)聲明如下：
/*2.5 尋找最大的K個數(shù)*/
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);
源代碼如下：
/*第一種解法不好的地方在于它改變了數(shù)組中原來數(shù)的順序*/
/*
*第二種解法利用最小堆的思想尋找TOPK，是經(jīng)典的大數(shù)據(jù)解題方法，
*網(wǎng)絡上很多類似的解釋，這里，不做過多的解釋
*/
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);
}
}
}
}
生活不易，碼農(nóng)辛苦
如果您覺得本網(wǎng)站對您的學習有所幫助,可以手機掃描二維碼進行捐贈
