2020年Java程序員面試算法寶典附答案，眾所周知，算法可以說(shuō)是大廠面試Java程序員的必問(wèn)面試題。相信算法的重要性大家都了解，好的算法可以讓性能得到萬(wàn)倍提升，做到毫秒級(jí)處理千萬(wàn)數(shù)據(jù)的程度。因此，為了提升大家在面試中的底氣，跟著小編往下看：

    1、算法的時(shí)間復(fù)雜度時(shí)候是什么？

    答案：算法的時(shí)間復(fù)雜度表示程序運(yùn)行完成所需的總時(shí)間，它通常用大O表示法來(lái)表示。

    2、合并k個(gè)有序（假設(shè)升序）數(shù)組的具體步驟是什么？

    答案：將k個(gè)數(shù)組的第一個(gè)元素取出來(lái)，維護(hù)一個(gè)小頂堆；彈出堆頂元素存入結(jié)果數(shù)組中，并把該元素所在數(shù)組的下一個(gè)元素取出來(lái)壓入隊(duì)中；調(diào)整堆的結(jié)構(gòu)，使其滿足小頂堆的定義；重復(fù)前兩步直到合并完成。

    3、解釋二分法檢索如何工作？

    答案：在二分法檢索中，我們先確定數(shù)組的中間位置，然后將要查找的值與數(shù)組中間位置的值進(jìn)行比較，若小于數(shù)組中間值，則要查找的值應(yīng)位于該中間值之前，依此類推，不斷縮小查找范圍，直至得到最終結(jié)果。

    代碼拓展，二分法查找

    defBinarySearch(t,x):

    t.sort()#對(duì)列表進(jìn)行排序，列表是有序的，是二分法的前提

    low=0;

    high=len(t)-1;

    whilelow<high:

    mid=(low+high)/2;

    ift[mid]<x:

    low=mid+1;

    elift[mid]>x:

    high=mid-1;

    else:

    returnmid

    returnNon

    4、查找數(shù)組中出現(xiàn)次數(shù)超過(guò)一半的數(shù)字

    答案：等價(jià)于求數(shù)組中第n/2大的數(shù)，和4中思想一樣，平均時(shí)間復(fù)雜度O(n)

    5、一個(gè)數(shù)組怎么輸出前K大的值、時(shí)間復(fù)雜度？

    答案：借助快排partition的思想，平均時(shí)間復(fù)雜度是O(n)

    6、用A表示1第一列，B表示2第二列，。。。，Z表示26，AA表示27，AB表示28。。。以此類推。請(qǐng)寫(xiě)出一個(gè)函數(shù)，輸入用字母表示的列號(hào)編碼，輸出它是第幾列。

    答案：這道題的解題思路關(guān)鍵在于26進(jìn)制轉(zhuǎn)10進(jìn)制。

    7、輸入一個(gè)正數(shù)n，輸出所有和為n連續(xù)正數(shù)序列。

    答案：輸入15，由于1+2+3+4+5=4+5+6=7+8=15，所以輸出3個(gè)連續(xù)序列1-5、4-6和7-8。

    8、輸出一個(gè)整數(shù)二進(jìn)制表示中1的個(gè)數(shù)。

    答案：這道題的解法多樣，可以右移原數(shù)判斷，如果輸入是負(fù)數(shù)可能陷入死循環(huán)；也可以左移1；還可以把一個(gè)整數(shù)-1后與原數(shù)做與運(yùn)算會(huì)消去原數(shù)最左邊的1。

    9、在一個(gè)二維數(shù)組中（每個(gè)一維數(shù)組的長(zhǎng)度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請(qǐng)完成一個(gè)函數(shù)，輸入這樣的一個(gè)二維數(shù)組和一個(gè)整數(shù)，判斷數(shù)組中是否含有該整數(shù)。

    答案：這道算法面試題對(duì)大多數(shù)Java程序員來(lái)講并不難，大致的解題思路如下，我們注意到這個(gè)二維數(shù)組的行和列都是升序的，也就是說(shuō)最上面的一行和最右邊的一列在整體上也是升序的，在一個(gè)排序數(shù)組上查找某個(gè)我們會(huì)很自然的想起二分法。這樣我們每次都把要查找的數(shù)和當(dāng)前剩下的二維數(shù)組的右上角數(shù)字比較，這樣每次我們都可以排除掉一行或一列。算法的時(shí)間復(fù)雜度是O(n+m)，也就是行數(shù)加列數(shù)。

    10、兩個(gè)排序數(shù)組A1和A2，現(xiàn)在想把A2插入A1中并仍保持有序。

    答案：數(shù)組是個(gè)順序表，我們往數(shù)組中插入某個(gè)數(shù)的話必須要移動(dòng)當(dāng)前位置后面所有的數(shù)。常規(guī)的思路是每次插入一個(gè)數(shù)并移動(dòng)后面的數(shù)，這樣多次插入后會(huì)導(dǎo)致數(shù)組中有的數(shù)被移動(dòng)了多次，極大浪費(fèi)了效率。我們希望每個(gè)數(shù)移動(dòng)一次就到達(dá)它最終的位置，所以我們往往會(huì)反向移動(dòng)數(shù)組，這樣做的好處是移動(dòng)當(dāng)前數(shù)時(shí)后面的數(shù)已經(jīng)到達(dá)了最終位置，我們移動(dòng)當(dāng)前數(shù)不會(huì)影響到后面的數(shù)，這樣就確保了每個(gè)數(shù)只被移動(dòng)一次。

　以上就是動(dòng)力節(jié)點(diǎn)java培訓(xùn)機(jī)構(gòu)的小編針對(duì)“2020年Java程序員面試算法寶典附答案”的內(nèi)容進(jìn)行的回答，希望對(duì)大家有所幫助，如有疑問(wèn)，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。