- 相關(guān)推薦
常見的算法面試題
算法面試題中經(jīng)常出現(xiàn)的一種題目就是查找或者是排序. 個人感覺有80%的題目都和查找排序有關(guān),大部分常用的排序算法時間復(fù)雜度都是O(nLogn)。這個只能說是通用解,一般解,對于算法面試題中往往要求很低的時間復(fù)雜度!
例如下面這個題目
已知一個數(shù)組長為m 中間存放的都是整數(shù) 其值范圍為1-m ,中間的元素有可能重復(fù) 也有可能不重復(fù)
如何在O(M)的情況下查到 (1-m)的數(shù)中 哪些數(shù)重復(fù)了,哪些數(shù)沒有出現(xiàn)
counting sort 的本質(zhì)是 新建一個長度為M的數(shù)組An 每一個數(shù)組下標(biāo)代表一個數(shù) ,數(shù)組中的值代表這個元素出現(xiàn)的次數(shù) (初始值都為0)
那么, 遍歷一次m 遇到一個數(shù) 就在對應(yīng)的下標(biāo)上加1
那么最終可以得到一個An 其中包含了所有元素的出現(xiàn)個數(shù)
將其展開 就可以獲得排序完的數(shù)組
這是一種特殊的算法,只能解決特殊的問題 但是他的時間復(fù)雜度是O(n)
如果在你遇到排序 或者查找之類的算法題的時候,不如上去先試試counting sort
相關(guān)文章分享:
http://m.ardmore-hotel.com/
【常見的算法面試題】相關(guān)文章:
java算法面試常見問題08-05
明基常見面試題08-06
常見護(hù)士面試題目及答案08-09
常見面試題目及解析08-22
名校英語面試經(jīng)典常見的面試題09-25
汽車銷售應(yīng)聘常見面試題09-25
應(yīng)聘淘寶客服的常見面試題08-07
常見的企業(yè)面試題目有哪些08-22
跳槽求職者常見面試題09-21
哈佛大學(xué)常見的5類面試題型08-22