如果不限定條件的話，這個(gè)問題還是很好解決的，但是當(dāng)我們要求時(shí)間復(fù)雜度為O(N)，空間復(fù)雜度為O(1)時(shí)，問題就沒那么好解決了。

成都創(chuàng)新互聯(lián)公司-專業(yè)網(wǎng)站定制、快速模板網(wǎng)站建設(shè)、高性價(jià)比潁上網(wǎng)站開發(fā)、企業(yè)建站全套包干低至880元,成熟完善的模板庫,直接使用。一站式潁上網(wǎng)站制作公司更省心,省錢,快速模板網(wǎng)站建設(shè)找我們，業(yè)務(wù)覆蓋潁上地區(qū)。費(fèi)用合理售后完善，10年實(shí)體公司更值得信賴。

   簡單的思路就是，創(chuàng)建一個(gè)大小為K=100的小堆，調(diào)整好，然后從K開始拿十萬個(gè)數(shù)據(jù)一個(gè)一個(gè)跟堆頭比較，如果比堆頭大，就入堆，然后調(diào)整成最小堆，一直循環(huán)到第N=100000個(gè)數(shù)據(jù)。

void AdjustDown(int* _a, size_t size,int i)
{
    int parent = i;
    int child = 2 * parent + 1;
    while (child < size)
    {
        //找出孩子中的最小值
        if (child + 1 < size && _a[child + 1] < _a[child])
        {
            ++child;
        }
        //與父節(jié)點(diǎn)做比較
        if (_a[parent] > _a[child])
        {
            swap(_a[parent], _a[child]);
            parent = child;
            child = parent * 2 + 1;
        }
        else
        {
            break;
        }
    }
}

//找N個(gè)數(shù)據(jù)中的大K個(gè)
int* GetKTop(int* a,size_t size,size_t n)
{
    int* _a = new int[size];
    for (int i = 0; i < size; i++)
    {
        _a[i] = a[i];
    }

    //建堆
    for (int i = (size - 2) / 2; i >= 0; i--)
    {
        AdjustDown(_a, size,i);
    }

    for (int i = 0; i < n - size; i++)
    {
        if (_a[0] < a[size + i])
        {
            _a[0] = a[size + i];
            AdjustDown(_a, size, 0);
        }
    }
    return _a;
}

void _AdjustDown(int* a, size_t size, int i)
{
    int parent = i;
    int child = 2 * parent + 1;
    while (child < size)
    {
        //找出孩子中的大值
        if (child + 1 < size && a[child] < a[child + 1])
        {
            ++child;
        }
        //拿父節(jié)點(diǎn)與大子節(jié)點(diǎn)做比較
        if (a[parent] < a[child])
        {
            swap(a[parent], a[child]);
            parent = child;
            child = 2 * parent + 1;
        }
        else
        {
            break;
        }
    }
}

創(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ù)器買多久送多久。

網(wǎng)站名稱：【數(shù)據(jù)結(jié)構(gòu)】【面試題】找N個(gè)數(shù)據(jù)中最大的K個(gè)數(shù)據(jù)-創(chuàng)新互聯(lián)
文章轉(zhuǎn)載：http://weahome.cn/article/pshhs.html