首頁(yè) 猿問(wèn) 有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)...

有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)，如何用最快的方法取出其中最大的三個(gè)數(shù)。

Java

BIG陽(yáng) 2019-03-13 18:15:40

最近有一個(gè)java大神，是螞蟻支付寶的哦，問(wèn)了我這么一個(gè)問(wèn)題。我的回答是先將數(shù)組分解成兩百個(gè)小數(shù)組或者更多，在開(kāi)兩百個(gè)thread進(jìn)行排序，取最大，然后對(duì)這兩百個(gè)數(shù)進(jìn)行排序，取前三。其實(shí)我的思路根本就沒(méi)有涉及到算法層面，也只是暴力破解。其實(shí)這不是最好的做法，因?yàn)檫@樣會(huì)嚴(yán)重的浪費(fèi)資源，然后他的回答是堆排序。我的問(wèn)題是堆排序是怎樣實(shí)現(xiàn)的，最好用代碼體現(xiàn)出來(lái)。

查看完整描述

8 回答

30秒到達(dá)戰(zhàn)場(chǎng)

TA貢獻(xiàn)1828條經(jīng)驗(yàn) 獲得超6個(gè)贊

有N(N>>10000)個(gè)整數(shù),求出其中的前K個(gè)最大的數(shù)。（稱(chēng)作Top k算法問(wèn)題）。由于(1)輸入的大量數(shù)據(jù)；(2)只要前K個(gè)，對(duì)整個(gè)輸入數(shù)據(jù)的保存和排序是相當(dāng)?shù)牟豢扇〉?。可以利用?shù)據(jù)結(jié)構(gòu)的最小堆來(lái)處理該問(wèn)題。

最小堆，對(duì)于每個(gè)非葉子節(jié)點(diǎn)的數(shù)值，一定不大于孩子節(jié)點(diǎn)的數(shù)值。這樣可用含有K個(gè)節(jié)點(diǎn)的最小堆來(lái)保存K個(gè)目前的最大值(當(dāng)然根節(jié)點(diǎn)是其中的最小數(shù)值)。每次有數(shù)據(jù)輸入的時(shí)候可以先與根節(jié)點(diǎn)比較。若不大于根節(jié)點(diǎn)，則舍棄；否則用新數(shù)值替換根節(jié)點(diǎn)數(shù)值。并進(jìn)行最小堆的調(diào)整。

由于僅僅保存了K個(gè)數(shù)據(jù)，有調(diào)整最小堆的時(shí)間復(fù)雜度為O(logK)，因此TOp K算法(問(wèn)題)時(shí)間復(fù)雜度為O(nlogK).

1 反對(duì) 回復(fù) 2019-04-19

慕后森

TA貢獻(xiàn)1802條經(jīng)驗(yàn) 獲得超5個(gè)贊

這不是典型的Top k問(wèn)題嗎，你可以百度一下Top K

反對(duì) 回復(fù) 2019-04-19

Smart貓小萌

TA貢獻(xiàn)1911條經(jīng)驗(yàn) 獲得超7個(gè)贊

topn的如果說(shuō)穩(wěn)妥的答案堆排是沒(méi)有錯(cuò)的問(wèn)題是這個(gè)3取的。。。這么小的數(shù)

反對(duì) 回復(fù) 2019-04-19

互換的青春

TA貢獻(xiàn)1797條經(jīng)驗(yàn) 獲得超6個(gè)贊

就是堆排序a

反對(duì) 回復(fù) 2019-04-19

慕神8447489

TA貢獻(xiàn)1780條經(jīng)驗(yàn) 獲得超1個(gè)贊

topk求解

反對(duì) 回復(fù) 2019-04-19

嗶嗶one

TA貢獻(xiàn)1854條經(jīng)驗(yàn) 獲得超8個(gè)贊

你要的堆排，JAVA

public class 堆排 {

public static void main(String[] args) {

int [] arr= {0,5,3,2,6,7};

HeapSort(arr);

for(int s:arr){

System.out.println(s);

}

public static void BuildHeap(int[] arr,int s,int length){

int temp = arr[s];

for(int j = s*2 +1 ; j<length;j = j*2 +1){

if(j+1<length && arr[j]>arr[j+1]){

j++;

}

if(temp < arr[j]){

break;

}

arr[s] = arr[j];

s = j;

}

arr[s] = temp;

}

public static void HeapSort(int[] arr){

for(int i = (arr.length)/2-1;i>=0;i--){

BuildHeap(arr, i, arr.length);

}

for(int i = arr.length - 1;i>=0;i--){

if(arr[0]!= arr[i]){

arr[i] ^= arr[0];

arr[0] ^= arr[i];

arr[i] ^= arr[0];

}

BuildHeap(arr, 0, i);

}

反對(duì) 回復(fù) 2019-04-19

8 回答
0 關(guān)注
739 瀏覽

關(guān)注

添加回答

舉報(bào)

0/150

提交

取消

使用 Ctrl+D 可將網(wǎng)站添加到書(shū)簽

微信客服

購(gòu)課補(bǔ)貼
聯(lián)系客服咨詢優(yōu)惠詳情

幫助反饋 APP下載

慕課網(wǎng)APP
您的移動(dòng)學(xué)習(xí)伙伴

公眾號(hào)

掃描二維碼
關(guān)注慕課網(wǎng)微信公眾號(hào)

第七色在线视频,2021少妇久久久久久久久久,亚洲欧洲精品成人久久av18,亚洲国产精品特色大片观看完整版,孙宇晨将参加特朗普的晚宴

熱搜

最近搜索清空

有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)，如何用最快的方法取出其中最大的三個(gè)數(shù)。

有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)，如何用最快的方法取出其中最大的三個(gè)數(shù)。

8 回答

添加回答

有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)，如何用最快的方法取出其中最大的三個(gè)數(shù)。

有一個(gè)算法問(wèn)題想請(qǐng)教，給定一億個(gè)數(shù)，如何用最快的方法取出其中最大的三個(gè)數(shù)。