【正文】
所有的元素。當(dāng)然,僅僅這個(gè)還是不夠的:將所有的數(shù)都導(dǎo)入塊狀鏈表,而且,對于鏈表里的每一個(gè)塊,都維護(hù)一個(gè)排序后的表。這個(gè)表的 Replace Element仍然可以在 Sqrt(n)時(shí)間內(nèi)解決。然后,如黃剛同學(xué)所說,二分那個(gè)所求的最大值,然后可以輕松地掃描塊,并統(tǒng)計(jì)出那個(gè)數(shù)是否為第 k大,問題解決,時(shí)間復(fù)雜度為 No gM a x L o ngo gNBNo gM a x L o ngloglNNNl)N*loglN*(A???看起來,這似乎比黃剛同學(xué)的算法要慢一個(gè)數(shù)量級??墒牵S護(hù)平衡樹和線段樹的代價(jià)是很大的! 塊狀鏈表的出色表現(xiàn)說明,有時(shí)候,某個(gè)問題,并不是漸進(jìn)意義復(fù)雜度小的辦法,就是最好的!