題目
Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.
思路
將數(shù)組中的k個(gè)有序鏈表歸并成一個(gè)有序鏈表，并分析時(shí)間復(fù)雜度真朗。該題可以在第22題-"merge two sorted lists"的基礎(chǔ)上設(shè)計(jì)算法荞驴。
一開始想到遍歷數(shù)組的k-1個(gè)鏈表叫搁，將第一個(gè)鏈表與第二個(gè)鏈表合并成一個(gè)新鏈表蚤氏，然后第三個(gè)鏈表再跟這個(gè)新鏈表合并成新鏈表锻弓，以此類推......假設(shè)鏈表長度最長為n辣辫，則這樣設(shè)計(jì)出來的算法時(shí)間復(fù)雜度為O(nk)戚扳，提交報(bào)超時(shí)錯(cuò)誤忧便。
改變思路，不要用單一遍歷方式帽借≈樵觯可以遞歸歸并數(shù)組中的k個(gè)鏈表，將其分割成k/2大小的數(shù)組歸并砍艾，然后再分成k/2^2大小的數(shù)組歸并......這樣遞歸歸并的時(shí)間復(fù)雜度為O(logk)蒂教，總時(shí)間復(fù)雜度為O(nlogk)
