問題是：給你一個數(shù)組，求解出現(xiàn)次數(shù)第K多的元素。當(dāng)然leetcode上的要求是算法復(fù)雜度不能大于O(N*logN)。

首先這個問題我先是在leetcode上看到，當(dāng)時想了兩種做法，做到一半都覺得不是很好，正在思考別的方法。然后在牛客網(wǎng)上看別人的面試經(jīng)歷，看到一個應(yīng)聘者和用我?guī)缀跬耆粯拥乃悸穱L試在面試中解決這個問題（HashMap-->TreeSet），但是都沒解決出來。這個問題確實(shí)是一個乍看不難但是要實(shí)際解決又會不停發(fā)現(xiàn)自己思路有問題的問題，于是我索性記錄一下這兩種想法和解決之道。

拿到這個問題的時候我第一時間想到了用HashMap解決，鍵值對的鍵是數(shù)組中的元素的值，值是目前出現(xiàn)的次數(shù)，當(dāng)?shù)谝淮纬霈F(xiàn)的時候值給1，以后發(fā)現(xiàn)已經(jīng)存在那么就取出值加1再放進(jìn)去。這個方法的思想是用類似于上一篇博文中的方法來做。核心是用hash算法形成一個元素與儲存位置的映射來實(shí)現(xiàn)查找操作的常量時間復(fù)雜度。這么做的結(jié)果是你能在O(N)的算法復(fù)雜度情況下得到一個HashMap，它儲存了每一種元素和其出現(xiàn)的個數(shù)。這個時候一個很具體的問題就出現(xiàn)了，下一步本來需要對出現(xiàn)次數(shù)進(jìn)行一個排序，然后取出出現(xiàn)次數(shù)第K大的那個元素。但是問題是鍵值對的映射方式是從鍵映射到值，也就是說你用HashMap可以找出值的集合，但是無法找出與這個值對于的鍵。比如你通過排序知道了最頻繁的次數(shù)是5，但是你不知道到底誰出現(xiàn)了5次。這個地方其實(shí)我要解釋一下，不是說你就完全做不到實(shí)現(xiàn)反映射，而是第一，HashMap實(shí)現(xiàn)的是映射你強(qiáng)行根據(jù)值尋找鍵不符合其設(shè)計初衷，第二，實(shí)現(xiàn)的過程比較復(fù)雜我想需要很大的算法復(fù)雜度完全抵消了使用HashMap帶來的好處。比如一個鍵只能對應(yīng)一個值，但是一個值可能有多個鍵對應(yīng)。（每一個數(shù)組中的元素都有確定的出現(xiàn)次數(shù)，但是出現(xiàn)次數(shù)為K的元素可能不止一個）。要解決這些問題等等。真的解決了也就不是這道題目的問題了。

第二時間我想到了用TreeSet，因?yàn)樗瓤梢愿鶕?jù)你的重寫的equal()方法判斷是否等于和去重，又可以對你輸入數(shù)據(jù)用comparator進(jìn)行排序。我就想，我干脆寫一個類，里面即方數(shù)字本身用于比較是否相等（hashcode和equal），又放當(dāng)前出現(xiàn)的次數(shù)，又實(shí)現(xiàn)comparator接口來對當(dāng)前出現(xiàn)的次數(shù)進(jìn)行排序。我的期望是好的，但是在一開始的思考的時候我忽視了（確實(shí)沒想到）一個根本的問題，這個問題直接導(dǎo)致我的這個想法完全不能按照我設(shè)想的實(shí)現(xiàn)。隨著你遍歷的進(jìn)行，你的某個數(shù)的出現(xiàn)的次數(shù)可能從1變到2變到3。所以你有一個不停動態(tài)修改TreeSet的內(nèi)容對象的過程。但是你無法獲得TreeSet中值為當(dāng)前數(shù)組值的那個對象的引用。比如說我現(xiàn)在遍歷到數(shù)組中的5這個元素，于是我去TreeSet中找值為5的對象，但是找不到(沒有提供相應(yīng)的方法)。當(dāng)然確實(shí)也不應(yīng)該有這樣的方法，你想你都知道值是5了，可是你又不知道具體引用的值，TreeSet也沒辦法幫你。如果用遍歷強(qiáng)行去找會導(dǎo)致一個很復(fù)雜的過程，算法復(fù)雜度高（紅黑樹的遍歷）。同時，TreeSet是按照某種規(guī)律排序的，大量的修改其值的操作（通過先刪除再add，或者這個問題中的用add覆蓋）會影響其效率因?yàn)橐S護(hù)某種順序。所以這個問題中也不推薦這么做。

雖然以上兩種做法都么能直接解決這個問題，但是給我?guī)砹怂伎肌?/p>

?最后還是做出來了，大致就是第一種方法不過鍵值對的值是我寫的類，最后再用堆排序。這個做法還是挺蠢得我覺得。貌似最佳做法使用桶排序O(N)?以后再研究研究這個。

轉(zhuǎn)載于:https://www.cnblogs.com/dsj2016/p/5501663.html

總結(jié)

以上是生活随笔為你收集整理的寻找数组中第K频繁的元素的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。