{"id":2553,"date":"2018-05-02T23:21:12","date_gmt":"2018-05-02T15:21:12","guid":{"rendered":"https:\/\/boweihe.me\/?p=2553"},"modified":"2018-05-02T23:21:12","modified_gmt":"2018-05-02T15:21:12","slug":"leetcode-347-top-k-frequent-elements","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2553","title":{"rendered":"LeetCode 347. Top K Frequent Elements"},"content":{"rendered":"<p>https:\/\/leetcode.com\/problems\/top-k-frequent-elements\/description\/<br \/>\nhash map + heap<br \/>\nTime complicity: O(N + logk)<\/p>\n<pre class=\"lang:c++ decode:true \">struct KvPair\n{\n    int key = 0;\n    int val = 0;\n};\nclass Solution {\npublic:\n    vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\n        unordered_map&lt;int, int&gt; counts;\n        for (int num : nums)\n        {\n            counts[num]++;\n        }\n        auto comp = [](const KvPair&amp; lhs, const KvPair&amp; rhs){\n            return lhs.val &gt; rhs.val;\n        };\n        priority_queue&lt;KvPair, vector&lt;KvPair&gt;, decltype(comp)&gt; pri_q(comp);\n        for (auto&amp; it : counts)\n        {\n            pri_q.push({it.first, it.second});\n            if (pri_q.size() &gt; k)\n                pri_q.pop();\n        }\n        vector&lt;int&gt; results;\n        while (!pri_q.empty())\n        {\n            results.push_back(pri_q.top().key);\n            pri_q.pop();\n        }\n        return results;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>https:\/\/leetcode.com\/problems\/top-k-frequent-elements\/description\/ hash map + heap Time complicity: O(N + logk) struct KvPair { int key = 0; int val = 0; }; class Solution { public: vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) { unordered_map&lt;int, int&gt; counts; for (int num : nums) { counts[num]++; } auto comp = [](const KvPair&amp; lhs, const KvPair&amp; rhs){ return lhs.val &gt; [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[1],"tags":[],"class_list":["post-2553","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2553","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=2553"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2553\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2553"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2553"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2553"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}