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