聽說讀寫

已知一個大小為M的數組  里面放著M個整數

現在要找出前n個最大的元素

問:

　　最優的算法,時間復雜度和空間復雜度

解法有很多,最好的不好找, 這里隨便先舉幾個一般的:

　　1.先給M的數組做一次排序 那么前n個元素就是結果, 假設用快速排序 那么時間復雜度就是 M*logM

　　2.已知使用冒泡法找出最大的一個元素, 需要M次, 那么找出N個,就需要M*N ,如果N很小這個算法就很優化

補充

以下是個人覺得最好的算法(快速排序的一部分)

隨機在m中挑選一個值,  然后比m小的放在m左邊, 比m大的放在m右邊

假設右邊有c個元素, 如果c小于5個, 在左邊的元素中繼續尋找 最大的n-c個元素, 

否則丟棄所有左側元素, 在右側中繼續尋找最大的n個元素

遞歸,不斷丟棄元素 直到最后找到所有的前n大元素