{"id":2018,"date":"2016-05-05T22:17:15","date_gmt":"2016-05-05T14:17:15","guid":{"rendered":"http:\/\/boweihe.me\/?p=2018"},"modified":"2016-05-05T22:17:15","modified_gmt":"2016-05-05T14:17:15","slug":"leetcode347-top-k-frequent-elements","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=2018","title":{"rendered":"LeetCode347. Top K Frequent Elements"},"content":{"rendered":"<p>\u597d\u4e45\u4e0d\u5237\u9898\u4e86\uff0c\u4eca\u665a\u6765\u4e00\u9053\u3002<\/p>\n<h3>\u9898\u76ee<\/h3>\n<p>Given a non-empty array of integers, return the <b><i>k<\/i><\/b> most frequent elements.<br \/>\nFor example,<br \/>\nGiven <code>[1,1,1,2,2,3]<\/code> and k = 2, return <code>[1,2]<\/code>.<br \/>\n<b>Note: <\/b><\/p>\n<ul>\n<li>You may assume <i>k<\/i> is always valid, 1 \u2264 <i>k<\/i> \u2264 number of unique elements.<\/li>\n<li>Your algorithm&#8217;s time complexity <b>must be<\/b> better than O(<i>n<\/i> log <i>n<\/i>), where <i>n<\/i> is the array&#8217;s size.<\/li>\n<\/ul>\n<h3>\u601d\u8def<\/h3>\n<p>\u9898\u76ee\u4e2d\u660e\u786e\u63d0\u793a\u8981O(nlogn)\u590d\u6742\u5ea6\u4e86&#8230;<br \/>\n\u6211\u7684\u505a\u6cd5\u662f\u5148\u7edf\u8ba1\u7ed3\u679c\u5230\u4e00\u4e2amap&lt;value, count&gt;\u91cc\u9762\uff0c\u7136\u540e\u7528\u4e00\u4e2a\u5927\u5c0f\u4e3ak\u7684\u6700\u5c0f\u5806\u5904\u7406\uff0c\u6bcf\u6b21\u4ecemap\u4e2d\u8bfb\u53d6\u5143\u7d20\u65f6\u6839\u636ecount\u503c\u5224\u65ad\u662f\u5426\u8981\u66ff\u6362\u6389\u5806\u9876\u3002\u7531\u4e8eSTL\u7684map\u662f\u7528\u7ea2\u9ed1\u6811\u5b9e\u73b0\u7684\uff0c\u6240\u4ee5\u65f6\u95f4\u590d\u6742\u5ea6\u5c31\u4fdd\u8bc1\u4e86\uff0c\u8981\u518d\u5feb\u7684\u8bdd\u5c31\u76f4\u63a5\u7528hash\u51fd\u6570\u5427\uff0c\u53ef\u4ee5\u5230O(n)\u3002\u7ef4\u62a4k\u5927\u5c0f\u7684\u5806\uff0c\u7b97\u6700\u5dee\u60c5\u51b5\uff0c\u5efa\u5806\u590d\u6742\u5ea6\u662fO(k)\uff0c\u7ef4\u62a4\u590d\u6742\u5ea6\u662fO(logk), \u8981\u7ef4\u62a4M-k\u6b21\uff0c\u5176\u4e2d0&lt;M&lt;=N\u662fmap\u4e2d\u7684\u5143\u7d20\u4e2a\u6570.<br \/>\n<strong>\u4ee3\u7801<\/strong><\/p>\n<pre class=\"lang:c++ decode:true \">struct CountVal{\n    int val;\n    int count;\n    CountVal(int _val, int _count){\n        val = _val;\n        count = _count;\n    }\n};\nbool compareObj(const CountVal&amp; x, const CountVal&amp; y){\n    return x.count &gt; y.count;\n}\nclass Solution {\npublic:\n    vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\n        map&lt;int, int&gt; countMap;\n        vector&lt;CountVal&gt; counts;\n        for(int i=0; i&lt;nums.size(); i++){\n            if(countMap.count(nums[i]) == 0)\n                countMap[nums[i]] = 1;\n            else\n                countMap[nums[i]]++;\n        }\n        int count = 0;\n        for(auto it=countMap.begin(); it!=countMap.end(); it++){\n            CountVal item(it-&gt;first, it-&gt;second);\n            if(count &lt; k){\n                counts.push_back(item);\n                if(count == k-1){\n                    make_heap(counts.begin(), counts.end(), compareObj);\n                }\n            } else {\n                if (it-&gt;second &gt; counts.front().count) {\n                    pop_heap(counts.begin(), counts.end(), compareObj);\n                    counts.pop_back();\n                    counts.push_back(item);\n                    push_heap(counts.begin(), counts.end(), compareObj);\n                }\n            }\n            count++;\n        }\n        vector&lt;int&gt; results;\n        for(auto it=counts.begin(); it!=counts.end(); it++){\n            results.push_back(it-&gt;val);\n        }\n        return results;\n    }\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u597d\u4e45\u4e0d\u5237\u9898\u4e86\uff0c\u4eca\u665a\u6765\u4e00\u9053\u3002 \u9898\u76ee Given a non-empty array of integers, return the k most frequent elements. For example, Given [1,1,1,2,2,3] and k = 2, return [1,2]. Note: You may assume k is always valid, 1 \u2264 k \u2264 number of unique elements. Your algorithm&#8217;s time complexity must be better than O(n log n), where n is the [&hellip;]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4],"tags":[66,112,186],"class_list":["post-2018","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-top-k","tag-186"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2018","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=2018"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/2018\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=2018"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=2018"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=2018"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}