代碼隨想錄打卡第13天 239. 滑動窗口最大值347. 前 K 個高頻元素

239. 滑動窗口最大值

題目鏈接:

https://leetcode.cn/problems/sliding-window-maximum/

算法思想

使用隊列實現(xiàn)滞谢。最簡單的思路就是雙重循環(huán)擎颖,時間復雜度是nxk扔罪,超時做瞪。

可以使用雙頭隊列deque實現(xiàn)妹田。自定義一個雙頭隊列带膀,隊列中維護一組單調遞減的數(shù)據(jù),每次獲取最大值,只要獲取隊頭的值即可香嗓。

代碼:

class Solution {

public:

? ? class max_queue{

? ? ? ? private:

? ? ? ? ? ? deque<int> d;

? ? ? ? public:

? ? ? ? void pop(int value) {

? ? ? ? ? ? if (!d.empty() && value == d.front()) {

? ? ? ? ? ? ? ? d.pop_front();

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? ? ? void push(int val)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? while(!d.empty() && d.back() < val)

? ? ? ? ? ? ? ? {

? ? ? ? ? ? ? ? ? ? // cout<<"d.pop_front:"<<d.front()<<endl;

? ? ? ? ? ? ? ? ? ? d.pop_back();


? ? ? ? ? ? ? ? }

? ? ? ? ? ? ? ? d.push_back(val);

? ? ? ? ? ? ? ? // cout<<"d.push_back"<<val<<endl;

? ? ? ? ? ? }

? ? ? ? ? ? int get_max_val()

? ? ? ? ? ? {

? ? ? ? ? ? ? ? return d.front();

? ? ? ? ? ? }

? ? ? ? };

? ? vector<int> maxSlidingWindow(vector<int>& nums, int k) {

? ? ? ? max_queue? max_q;

? ? ? ? int len = nums.size();

? ? ? ? vector<int> res;

? ? ? ? for(int i=0;i<k;i++)

? ? ? ? {

? ? ? ? ? ? max_q.push(nums[i]);

? ? ? ? }

? ? ? ? int max_value = max_q.get_max_val();

? ? ? ? ? ? // cout<<"max_value:"<<max_value<<endl;

? ? ? ? res.push_back(max_value);

? ? ? ? for(int i=k;i<len;i++)

? ? ? ? {

? ? ? ? ? ? cout<<"i:"<<i<<endl;

? ? ? ? ? ? max_q.pop(nums[i-k]);

? ? ? ? ? ? max_q.push(nums[i]);


? ? ? ? ? ? int max_value = max_q.get_max_val();

? ? ? ? ? ? // cout<<"max_value:"<<max_value<<endl;

? ? ? ? ? ? res.push_back(max_value);


? ? ? ? }

? ? ? ? return res;

? ? }

};

347. 前 K 個高頻元素

代碼鏈接:https://leetcode.cn/problems/top-k-frequent-elements/

算法思路:

最前k的最大頻率元素迅腔。

首先使用map進行頻率的統(tǒng)計,

其次靠娱,維護一個k個元素的小頂堆沧烈。為什么使用小頂堆呢?因為小頂堆pop()的時候像云,彈出最小元素锌雀,最后就留了前k個大的元素。

代碼:

class Solution {

public:

? ? class mycomparison{

? ? public:

? ? ? ? bool operator()(const pair<int, int>& lhs, const pair<int, int>& rhs) {

? ? ? ? ? ? return lhs.second > rhs.second;

? ? ? ? }

? ? };

? ? vector<int> topKFrequent(vector<int>& nums, int k) {

? ? ? ? unordered_map<int,int> m;

? ? ? ? int len = nums.size();

? ? ? ? for(int i=0;i<len;i++)

? ? ? ? {

? ? ? ? ? ? if(m.find(nums[i])==m.end())

? ? ? ? ? ? ? ? m[nums[i]] = 0;

? ? ? ? ? ? m[nums[i]] += 1;

? ? ? ? }

? ? ? ? priority_queue<pair<int,int>, vector<pair<int,int>>, mycomparison> pri;

? ? ? ? for(unordered_map<int,int>::iterator it = m.begin();it!=m.end();it++)

? ? ? ? {

? ? ? ? ? ? pri.push(*it);

? ? ? ? ? ? if(pri.size()>k)

? ? ? ? ? ? {

? ? ? ? ? ? ? ? pri.pop();

? ? ? ? ? ? }

? ? ? ? }

? ? ? ? vector<int> result(k);

? ? ? ? for(int i=0;i<k;i++)

? ? ? ? {

? ? ? ? ? ? result[i] = pri.top().first;

? ? ? ? ? ? pri.pop();

? ? ? ? }

? ? ? ? return result;

? ? }

};

?著作權歸作者所有,轉載或內容合作請聯(lián)系作者
  • 序言:七十年代末迅诬,一起剝皮案震驚了整個濱河市汤锨,隨后出現(xiàn)的幾起案子,更是在濱河造成了極大的恐慌百框,老刑警劉巖,帶你破解...
    沈念sama閱讀 222,464評論 6 517
  • 序言:濱河連續(xù)發(fā)生了三起死亡事件牍汹,死亡現(xiàn)場離奇詭異铐维,居然都是意外死亡,警方通過查閱死者的電腦和手機慎菲,發(fā)現(xiàn)死者居然都...
    沈念sama閱讀 95,033評論 3 399
  • 文/潘曉璐 我一進店門嫁蛇,熙熙樓的掌柜王于貴愁眉苦臉地迎上來,“玉大人露该,你說我怎么就攤上這事睬棚。” “怎么了解幼?”我有些...
    開封第一講書人閱讀 169,078評論 0 362
  • 文/不壞的土叔 我叫張陵抑党,是天一觀的道長。 經(jīng)常有香客問我撵摆,道長底靠,這世上最難降的妖魔是什么? 我笑而不...
    開封第一講書人閱讀 59,979評論 1 299
  • 正文 為了忘掉前任特铝,我火速辦了婚禮暑中,結果婚禮上,老公的妹妹穿的比我還像新娘鲫剿。我一直安慰自己鳄逾,他們只是感情好,可當我...
    茶點故事閱讀 69,001評論 6 398
  • 文/花漫 我一把揭開白布灵莲。 她就那樣靜靜地躺著雕凹,像睡著了一般。 火紅的嫁衣襯著肌膚如雪。 梳的紋絲不亂的頭發(fā)上请琳,一...
    開封第一講書人閱讀 52,584評論 1 312
  • 那天粱挡,我揣著相機與錄音,去河邊找鬼俄精。 笑死询筏,一個胖子當著我的面吹牛,可吹牛的內容都是我干的竖慧。 我是一名探鬼主播嫌套,決...
    沈念sama閱讀 41,085評論 3 422
  • 文/蒼蘭香墨 我猛地睜開眼,長吁一口氣:“原來是場噩夢啊……” “哼圾旨!你這毒婦竟也來了踱讨?” 一聲冷哼從身側響起,我...
    開封第一講書人閱讀 40,023評論 0 277
  • 序言:老撾萬榮一對情侶失蹤砍的,失蹤者是張志新(化名)和其女友劉穎痹筛,沒想到半個月后,有當?shù)厝嗽跇淞掷锇l(fā)現(xiàn)了一具尸體廓鞠,經(jīng)...
    沈念sama閱讀 46,555評論 1 319
  • 正文 獨居荒郊野嶺守林人離奇死亡帚稠,尸身上長有42處帶血的膿包…… 初始之章·張勛 以下內容為張勛視角 年9月15日...
    茶點故事閱讀 38,626評論 3 342
  • 正文 我和宋清朗相戀三年,在試婚紗的時候發(fā)現(xiàn)自己被綠了床佳。 大學時的朋友給我發(fā)了我未婚夫和他白月光在一起吃飯的照片滋早。...
    茶點故事閱讀 40,769評論 1 353
  • 序言:一個原本活蹦亂跳的男人離奇死亡,死狀恐怖砌们,靈堂內的尸體忽然破棺而出杆麸,到底是詐尸還是另有隱情,我是刑警寧澤浪感,帶...
    沈念sama閱讀 36,439評論 5 351
  • 正文 年R本政府宣布昔头,位于F島的核電站,受9級特大地震影響影兽,放射性物質發(fā)生泄漏减细。R本人自食惡果不足惜,卻給世界環(huán)境...
    茶點故事閱讀 42,115評論 3 335
  • 文/蒙蒙 一赢笨、第九天 我趴在偏房一處隱蔽的房頂上張望未蝌。 院中可真熱鬧,春花似錦茧妒、人聲如沸萧吠。這莊子的主人今日做“春日...
    開封第一講書人閱讀 32,601評論 0 25
  • 文/蒼蘭香墨 我抬頭看了看天上的太陽纸型。三九已至,卻和暖如春,著一層夾襖步出監(jiān)牢的瞬間狰腌,已是汗流浹背除破。 一陣腳步聲響...
    開封第一講書人閱讀 33,702評論 1 274
  • 我被黑心中介騙來泰國打工, 沒想到剛下飛機就差點兒被人妖公主榨干…… 1. 我叫王不留琼腔,地道東北人瑰枫。 一個月前我還...
    沈念sama閱讀 49,191評論 3 378
  • 正文 我出身青樓,卻偏偏與公主長得像丹莲,于是被迫代替她去往敵國和親光坝。 傳聞我的和親對象是個殘疾皇子,可洞房花燭夜當晚...
    茶點故事閱讀 45,781評論 2 361

推薦閱讀更多精彩內容