常見的算法面試題解法

　　大部分常用的排序算法時間復雜度都是O(nLogn)

　　這個只能說是通用解,一般解

　　對于算法面試題中往往要求很低的時間復雜度,

　　例如下面這個題目

　　已知一個數組長為m 中間存放的都是整數 其值范圍為1-m ,中間的元素有可能重復 也有可能不重復

　　如何在O(M)的情況下查到 (1-m)的數中 哪些數重復了,哪些數沒有出現

　　counting sort 的本質是 新建一個長度為M的`數組An 每一個數組下標代表一個數 ,數組中的值代表這個元素出現的次數 (初始值都為0)

　　那么, 遍歷一次m 遇到一個數 就在對應的下標上加1

　　那么最終可以得到一個An 其中包含了所有元素的出現個數

　　將其展開 就可以獲得排序完的數組

　　這是一種特殊的算法,只能解決特殊的問題 但是他的時間復雜度是O(n)

　　如果在你遇到排序 或者查找之類的算法題的時候,不如上去先試試counting sort

【常見的算法面試題解法】相關文章：

最常見的面試題09-17

4個常見的面試題08-08

常見的軟件測試面試題06-06

常見軟件測試面試題05-10

酒店銷售常見面試題08-11

常見面試題回答點評08-04

常見.net面試題及答案06-19

常見的企業面試題目有哪些08-11

常見的英語面試題目及技巧08-08