1.
排序，快速排序。
快速排序平均所費(fèi)時(shí)間為nlogn，從小到大排序這n個(gè)數(shù)，然后再遍歷序列中后k個(gè)元素輸出，即可，總的時(shí)間復(fù)雜度為O（nlogn+k）=O（n*logn）。
2.
堆排序 什么是堆?
維護(hù)k個(gè)元素的最小堆，原理與上述第2個(gè)方案一致，即用容量為k的最小堆存儲(chǔ)最先遍歷到的k個(gè)數(shù)，并假設(shè)它們即是最大的k個(gè)數(shù)，建堆費(fèi)時(shí)O（k），并調(diào)整堆（費(fèi)時(shí)O（logk））后，有k1>k2>…kmin（kmin設(shè)為小頂堆中最小元素）。繼續(xù)遍歷數(shù)列，每次遍歷一個(gè)元素x，與堆頂元素比較，若x>kmin，則更新堆（用時(shí)logk），否則不更新堆。這樣下來(lái)，總費(fèi)時(shí)O（klogk+（n-k）logk）=O（nlogk）。此方法得益于在堆中，查找等各項(xiàng)操作時(shí)間復(fù)雜度均為logk（不然，就如上述思路2所述：直接用數(shù)組也可以找出最大的k個(gè)元素，用時(shí)O（nk））。
核心思想：分治法 聊聊分治算法
采用分治算法解決的問(wèn)題需要滿足的條件(特征):
- . 原問(wèn)題規(guī)模通常比較大，不易直接解決，但問(wèn)題縮小到一定程度就能較容易的解決。
- . 問(wèn)題可以分解為若干規(guī)模較小、求解方式相同(似)的子問(wèn)題。且子問(wèn)題之間求解是獨(dú)立的互不影響。
- . 合并問(wèn)題分解的子問(wèn)題可以得到問(wèn)題的解。
