拿到這個(gè)題目我想到了很多方法，但是在我想到的方法中，要把在100萬個(gè)數(shù)中找到前k個(gè)數(shù)，都不適用。最后通過我的不斷研究，我想到了我認(rèn)為最簡單的方法，就是利用堆來做這道題目。
下面我分析一下我用堆排序的思路：
1.我先建一個(gè)大小為k的堆。
2.把100萬中前k個(gè)數(shù)放到這個(gè)堆中。
3.把這個(gè)堆調(diào)成小堆。
4.把100萬個(gè)從k到100萬之間的數(shù)字拿出來和堆的根結(jié)點(diǎn)作比較。
5.如果根結(jié)點(diǎn)小于這之間的某一個(gè)數(shù)，就把這個(gè)數(shù)拿給根結(jié)點(diǎn)，然后繼續(xù)調(diào)成小堆。否則繼續(xù)找
6.直到找完這100萬個(gè)數(shù)，堆中放的就是大的前k個(gè)數(shù)。
代碼如下：
重慶分公司
重慶分公司
//下調(diào)
void _AdjustDown(int *arr, int parent, int size)
{
int child = 2 * parent + 1;
while (child arr[child + 1])
{
child++;//保證是孩子結(jié)點(diǎn)大的一個(gè)節(jié)點(diǎn)
}
//交換
if (arr[child] < arr[parent])
{
swap(arr[child], arr[parent]);
parent = child;
child = 2 * parent + 1;
}
else
{
break;
}
}
}
int* Find(int *arr, int k,int N)
{
assert(arr);
assert(k > 0);
int *str = new int[k];
//把前k個(gè)元素放在堆中
for (int i = 0; i < k; i++)
{
str[i] = arr[i];
}
//調(diào)成最小堆
for (int j = (k - 2) / 2; j >= 0; j--)
{
_AdjustDown(str, j, k);
}
//然后k到N的所有數(shù)與堆中的根結(jié)點(diǎn)相比較
for (int n = k; n < N; n++)
{
if (str[0] < arr[n])//如果根結(jié)點(diǎn)小于堆中k到N中的某一元素
{
str[0] = arr[n];//把這個(gè)元素賦值給根結(jié)點(diǎn)
_AdjustDown(str, 0, k);//再一次調(diào)成最小堆
}
}
return str;
delete[]str;
} 希望這個(gè)對你們有幫助。期待你們的回復(fù)，有什么不對的地方可以指出來啊。
創(chuàng)新互聯(lián)www.cdcxhl.cn，專業(yè)提供香港、美國云服務(wù)器，動(dòng)態(tài)BGP最優(yōu)骨干路由自動(dòng)選擇，持續(xù)穩(wěn)定高效的網(wǎng)絡(luò)助力業(yè)務(wù)部署。公司持有工信部辦法的idc、isp許可證， 機(jī)房獨(dú)有T級(jí)流量清洗系統(tǒng)配攻擊溯源，準(zhǔn)確進(jìn)行流量調(diào)度，確保服務(wù)器高可用性。佳節(jié)活動(dòng)現(xiàn)已開啟，新人活動(dòng)云服務(wù)器買多久送多久。
