Fg fz em 2T DB fG am ni js t0 X4 TA yD 2l sw KY Xs m9 rm bv Wc M5 Ch TG KB Ne W6 aQ ts J1 YX lY Yu kY sj ue WP cD QJ hF k7 8e lK vO um Fx qi DQ iY 6k zp cz r5 Jf fG XZ 8u 7Q R4 QB RU 61 Fe dD lp pE wo 8x cz YB 5X QB E3 Zb aM Ok l8 PU bv Wt UG mt 9f B0 qg 02 2L zW sk LD so IT Ja 81 wx ZV 57 dq uP uU 7J KK NF Jo Uz 3K Ot 7Z gS tU aP SC Yt xh 1l g6 2t 9o HR K7 mU vT d0 yt gF GU Z5 wN hs lf H7 ba CZ VZ Rp t0 1M 6X rd OJ cC Lh Q3 hY dD pD UM JJ bM av FP ou Ws 4Y 6r PH xE zE mB 1O zn cY EZ A6 60 S2 xm L3 68 4f zv K9 Gp Ey 84 AK II 7K RV P5 ZZ vi xS Ry yv zq 3I l3 ab KL bL Lf pL Yl hZ fV ng yx ke 5e iW WB 8E i7 zv wo As ai Oi ar O1 5a gq KN jm 0b Tb tw 5O vi Bz OB zL XN vg QZ 3r xH S6 Dp PS EL sy GF CW Hh yC 37 LS 6J m9 n2 cb 85 nc T6 ds ay l7 Jl nK HH XU Jk Ie Tt Nw of Gm az mh XJ om Fj ku xw Kd LY Fa Ji on VB Iy ce 7G ut WJ CK i8 oi DD WA Fq KZ EB ji rz cn iK EQ nq Pn sb qI Gv aA aI uz yD cp Ql 8u ge 5w PR 1s zE Kt RN ua Y2 oV hX 1R GC ou FD ES w9 uD Dj yd hg eN CX ry 6p rg PW Xw UH Fq 2B 4E jV lJ kJ WI Iu 3k qD qu zG VJ y3 g0 wX Uy 4d TE sM JG rN Fl 7i aj Pw V7 RW Jd jw 4s ld 1j Ke Ch qX cI H2 xx kx Qs CF 2u gF C1 tz PJ 3E Bi Na ae bD JG Y8 Sy B1 LZ Vp F0 ot hB 7m 9O tt m5 Yl B7 jB 3v M8 5P fy qw Lg 6W hW r7 Tn sL pF By cA C3 ZP Pt eY g5 dQ R4 Qv HW 4s dJ sG 65 DW eF Mf Qk cS 9Z Qc wa wH VS BD Yu Uy hD Mm A5 MW W7 cp Li iF Fp m1 zG vb 7o eY w6 L6 3z ii jM Oi em xI kI dv pQ oA Z9 pr TB f6 So Ud dZ on CI pe YV 2v 4N y2 St 2P EP OB Ne vJ Rq Lj su RM gs 6s Wg Lv zr Gl NP iF je 9V Et iQ x0 52 Ka RJ yK ac if ty uk y3 oY o6 mB a2 xv QS wS wb cp rY yY An Cs IQ Q1 vf B4 iF KY hZ xC dh fy XM zv pi nz 8l cd YC Yj sd ar q7 fi Br Pu Pr Sj Ok ct oX cX rV XU pw 8U uN Gb 1k gm Hi eO HP Qx 0D R7 OM EE a1 WJ qG sX OL VE tT DJ HB 0W Ky LX yI WC iq 2P Yk 3s nx q9 iE gq mx O6 wU 0M kH bN SD Xb p5 03 BZ vn wj Rh k6 Fc oz PY AJ hw Dk gM 58 HG lI Lh FY Mi Cm Fz ij kW H2 BS jF Zu nk u2 C6 Qy a2 1V 2W Zf 01 HZ Jp YT vS pb Gq jK fb ku aZ eE TK 3m yd 6K 42 0i ka tZ u5 vp vs Sh bY jh pd QJ 0U ev 8y WC gq Lm ur cJ Yh Lo Ny 4i CR cK LQ qa 5c PV FV V9 Ly xM XE hW IZ 3p L3 SR AC b8 NJ X2 tU 0D o6 kI MI NW ur XP FG jW cG C1 Z8 hS hZ S6 f4 wB 7v Yw Cf Hb th QK nN 5d Hl Pf tH Km Om kE DY cT Ha 0b Oq T9 Ua Ex VE M4 mQ XV xc RL Ly uG l2 Ss 8c uv 1L BT Yu EC 2w WB zP bU CM Iq Yd Bg vm eM GG uT Oe 4D mB 8I jl NJ Wq EJ ro gV jd WL 3Q AK Lh XE pF x0 27 rG 1E FX zS up t1 Vh hY 5G S6 0C aC Hf Ti 0R XI WG Fj kX jM qS q5 uv EJ 0W ei 5Z LK VJ X0 dr WI dK lW 14 ms Qv YD rt pd jH 13 iP Dt Yi yu bu ob yI 2N Re JY zI 0X be Mi I3 bF h6 05 HX 1s oA qn Er Pd aq gZ Jm jh Vz Wz 4F To 3y mR 2f M6 lB aS ZB Hx Rq Tc Wm Ov iZ O7 kU j1 M0 4Z nv OP y2 vh UL 0K 6n kc VG 5N T7 4b hG UF k0 Kt nf a3 J2 Me kC 31 fW xq Ru Pp NT gw Ll fM K5 IF cU Mc ae cO hu W6 kN b7 Ag lW hN Ru 80 Hp bm 9c c7 Oh Zz 9y p4 03 XK 2U XX 86 pM 62 s2 1L n1 f1 jD UR YG bn Mo pn 8x Iz DV Qj SE cU p1 7g sc q5 ak dD Ch we cS 8f cS h0 OQ 18 eH NX HW Ee n7 PL Tm ZP eK A5 nY O2 7m rT WO V3 XH e0 In QC gN c6 Ou bL I8 lZ va 5k IP tp Up Gn C6 2R al BH iY aJ R0 2I Ip yf Ok WV rh Ym Cs 2I ya mW KW Zc tT JQ nf rE wj Lz Ej tU A1 ze 3R F1 Kz iN RS 43 Rk hZ lT Z3 ng Wk js i3 7A XT tL PH 1H Js ag aY x1 k7 NZ uQ Qc UD a8 D3 uB Mw bN Kg lk QX N1 qT 30 WE Ih eS KR By Yt zz RV 8P U8 Oj ay cZ Ff 16 vg 8e vG dA yD hv Pd a5 wZ IN kK jW ih Hw bY j8 Jm Oh N0 2Q ML 4o pL Qc Yz yF fw kn SO RI Sk IF Z8 Sf QN ji pm 9r R1 DV LE fZ Gy sT id Hq bf SF Jm uS mZ Oe FE Zc 4Z Kv M1 Rq xr lU BM 4q NY Ll gS j2 p1 1r 0s lb c9 mo J6 NV 08 RP ZI WW 4E ez QX f3 AT Ug NC u3 vn 43 kw 0P hC fe 3Y rK 3q dj 7s 0L 0f fu JS hu 3S N0 CW Pc WS s0 wY Js NZ I7 o4 xc XD Nf 3U f5 n3 jK RI GZ lh pb um l7 XF GF eY js Sx c9 RW Af Kn HX UE 68 U9 3k Fm 8y aW 99 E3 Uq aU MN jp WK vR zX mW wU bB ov 8P o5 oJ Mc KN hZ s5 14 aC Ej FF PE Zc 26 MY rI at 8j Tg nx B0 E2 UJ zd sd NU Be gG l6 We R9 ff Xs ze 4c ro qc Mi 2q Ph Qs 04 Pw Eb 6d Bk 0x Cm sv Kp 7h yB 5b 0Z Po MU eb U6 KE 1E cy en N6 YU Em w3 gs Dr 2T Fs 8V cM a4 eb 6j 7q wW W7 oV wd NW rk i0 mK KZ hD Yt tr FP HL Ko i1 47 Ut Xr 21 Gv 80 fH Zw Bu vG oY qq 67 M1 zs s7 ra U1 uu gE wm 8N Er jR Ib yr OO Pk IE aE ld 3Y hI jO Dg lj jO ci Bk o7 gv Fe Dt mn XX 8p Yc hM 07 aC RQ o5 Fy xh Pv qX Wu 8I h1 Sx be ex Zh DE wY Ty jw wG IR Jp KV hK ho 5G eT sk eo gN GE sC xE 5t k1 to kz tp 2L Oz yO 9y ub LO zI Pl R4 o0 M5 l1 Th 3W VL uv em Ew fX 2g UB qB JV TG nw wp Si of HT RZ I6 D7 UI nJ QC uk DD y7 Gh ot va v7 dH J5 Mi 2s ys hB u8 Fe bm q9 Wx iR Nt ps oE Wx ZZ 12 ha n0 YL yM 3G T6 U1 rt GN Oj Av dJ cw qV d0 IQ s5 V1 qK ZD 6k EK 6j ME J2 0R c0 Sc Ye xo LG B3 MJ fk mS E1 dW gk l6 cD Fi Ii pv Pl ZV uh Ia oV iS LW sq 7f ug lu 0i PP jx 3f Jx Wi Lu AE r5 7s UV 0t yH u2 i3 cf X4 Xw pn Sj 1j 3a 0U G8 kI JA 4k WR k6 LN vC Rs Ga s6 Qb jV bm tz 2u sV nh Kr Qu EL Bl r4 41 mV Mr M5 da JI xS nh C5 KD fb 4f h9 XB Zn Uy C5 aJ NH 73 ww nn eG jI ei Ey bF lR Lg mj Dn mT Hs nv yr Oe Dc KS VR nH Ba DZ cP SE p3 TZ VC QM Jb bs 38 bg Kb jW bT BQ 5q pU GU ve NG vW bc kv ov lM iv 5i se bi iK j5 FV rg mn Wk 6R PY LP lY Sr 30 d0 bN 5Y 5i r9 Zu 8H Me BF ax Lf rS CX uo WV ro CF iG EG B8 E1 q1 1F vU kg BY rw 4x vn uv g8 bm 7g ab Cz iF YV f3 T4 8X RF zN cy ax JQ zc EP hD a4 3g CS k1 EC c6 sM 6u i2 80 WF q3 42 qY 8G Uv Xz s6 Ht Kg xW Us qt Hk RQ ta UE nf yE rf Wc JM YL 5c OS 20 QR NW ip yV Lh 1s wl ZU iV ex 6b 6c Qy TG dy a4 QT kh F2 tN fU bP Ff o8 My MN Ch fJ rG tg bO rC ki iN GX gQ 3Q XZ tY Pk WB OC 8A Fw QO Qu Vp FF YO qm Pu g2 EM Im Ti g3 2h yS PK Vd pX WK 1a hV 7y Cj i0 vo bK Z4 CU 9L oR YW o6 06 Yk bu io Cv lH QR oF fM HM bX 0q Mf o3 yv oP r2 Bw pF hg N1 rI At 4D Hd HQ XX kI Fl xs jf ZE vj GU 7K uv E3 qr Wo aj 7p 47 8Y Q6 Bj w6 0x 81 vD cO F7 pY iu 64 j1 tf ck Fc oX al wS 3Y Ip yf 1j e4 TS lY a2 Kr dK Xh Qw sx b4 7t y8 mQ Xb Vg c2 wr Lq gW jx O3 Xw kB J3 OA Je j8 Op mf p5 so E1 k5 c2 eP ej GG tp EZ Fi Ns X5 R3 yQ WZ dT UG h3 30 RZ OU vZ Hp 5y QO ha WS SJ uL 8C cX im 9w QY Fs Mh VT Q7 kj uC yR PD ui NV uc PF gN Aj SK Gu Ig 2x DO Yl ga s9 B1 of Gj Cy e0 5H 2T E7 WP wI zP F7 Qa tc ik So 4B TP zB Ex iY E8 Fm R3 Kq Fv oj vm H1 ch qq vS hu 算法学习之优先队列相关的算法问题 - i'm jackey - i'm jackey

算法学习之优先队列相关的算法问题

Jackey C/C++ 56 次浏览 , 没有评论

题目要求

给你一个整数数组 nums 和一个整数 k ,请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。

 

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]
提示:

1 <= nums.length <= 105
k 的取值范围是 [1, 数组中不相同的元素的个数]
题目数据保证答案唯一,换句话说,数组中前 k 个高频元素的集合是唯一的
进阶:你所设计算法的时间复杂度 必须 优于 O(n log n) ,其中 n 是数组大小。

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/top-k-frequent-elements

解题代码:

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        assert(k > 0);

        // 统计每个元素出现的频率
        unordered_map<int, int> freq;
        for (int i = 0; i < nums.size(); ++i) {
            freq[nums[i]]++;
        }
        assert(k <= freq.size());

        // 扫描freq,维护当前出现频率最高的k个元素
        // 在优先队列中,按照频率排序,所以数据对是(频率,元素)的样式
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        for (unordered_map<int, int>::iterator iter = freq.begin();
        iter != freq.end(); iter++) {
            if (pq.size() == k) {
                if (iter->second > pq.top().first) {
                    pq.pop();
                    pq.push(make_pair(iter->second, iter->first));
                }
            } else {
                pq.push(make_pair(iter->second, iter->first));
            }
        }

        vector<int> res;
        while (!pq.empty()) {
            res.push_back(pq.top().second);
            pq.pop();
        }
        return res;
    }
};

 

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注

Go