{"id":669,"date":"2017-10-22T00:05:08","date_gmt":"2017-10-22T07:05:08","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=669"},"modified":"2018-08-30T13:33:47","modified_gmt":"2018-08-30T20:33:47","slug":"leetcode-347-top-k-frequent-elements","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-347-top-k-frequent-elements\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 347. Top K Frequent Elements"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 347. Top K Frequent Elements - \u5237\u9898\u627e\u5de5\u4f5c EP95\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/lm6pBga98-w?feature=oembed\" frameborder=\"0\" allow=\"accelerometer; autoplay; clipboard-write; encrypted-media; gyroscope; picture-in-picture; web-share\" referrerpolicy=\"strict-origin-when-cross-origin\" allowfullscreen><\/iframe><\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p>Given a non-empty array of integers, return the k most frequent elements.<\/p>\n<p>For example,<br \/>\nGiven [1,1,1,2,2,3] and k = 2, return [1,2].<\/p>\n<p>Note:<br \/>\nYou may assume k is always valid, 1 \u2264 k \u2264 number of unique elements.<br \/>\nYour algorithm&#8217;s time complexity must be better than O(n log n), where n is the array&#8217;s size.<\/p>\n<p><script async src=\"\/\/pagead2.googlesyndication.com\/pagead\/js\/adsbygoogle.js\"><\/script><br \/>\n<ins class=\"adsbygoogle\" style=\"display: block; text-align: center;\" data-ad-layout=\"in-article\" data-ad-format=\"fluid\" data-ad-client=\"ca-pub-2404451723245401\" data-ad-slot=\"7983117522\"><\/ins><br \/>\n<script>\n     (adsbygoogle = window.adsbygoogle || []).push({});\n<\/script><\/p>\n<p><strong>Idea:<\/strong><\/p>\n<p><a href=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95.png\"><img loading=\"lazy\" decoding=\"async\" class=\"alignnone size-full wp-image-677\" src=\"http:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95.png\" alt=\"\" width=\"960\" height=\"540\" srcset=\"https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95.png 960w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95-300x169.png 300w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95-768x432.png 768w, https:\/\/zxi.mytechroad.com\/blog\/wp-content\/uploads\/2017\/10\/347-ep95-624x351.png 624w\" sizes=\"auto, (max-width: 960px) 100vw, 960px\" \/><\/a><\/p>\n<p>&nbsp;<\/p>\n<h1>Solution 2: Priority queue \/ max heap<\/h1>\n<p>Time complexity: O(n) + O(nlogk)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">\/\/ Author: Huahuas\r\n\/\/ Running time: 16 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\r\n    unordered_map&lt;int, int&gt; count;        \r\n    for (const int num : nums)\r\n      ++count[num];\r\n    priority_queue&lt;pair&lt;int, int&gt;&gt; q;\r\n    for (const auto&amp; pair : count) {\r\n      q.emplace(-pair.second, pair.first);\r\n      if (q.size() &gt; k) q.pop();\r\n    }\r\n    vector&lt;int&gt; ans;\r\n    for (int i = 0; i &lt; k; ++i) {\r\n      ans.push_back(q.top().second);\r\n      q.pop();\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 56 ms\r\nclass Solution {\r\n  public List&lt;Integer&gt; topKFrequent(int[] nums, int k) {    \r\n    Map&lt;Integer, Integer&gt; counts = new HashMap&lt;&gt;();    \r\n    for (int num : nums)\r\n      counts.put(num, counts.getOrDefault(num, 0) + 1);    \r\n    \r\n    PriorityQueue&lt;int[]&gt; queue = new PriorityQueue&lt;&gt;((x, y) -&gt; x[0] - y[0]);\r\n    for (Integer num : counts.keySet()) {\r\n      queue.offer(new int[]{counts.get(num), num});\r\n      if (queue.size() &gt; k) queue.poll();\r\n    }\r\n        \r\n    List&lt;Integer&gt; ans = new ArrayList&lt;&gt;();\r\n    for (int i = 0; i &lt; k; ++i)\r\n      ans.add(queue.poll()[1]);\r\n    return ans;    \r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true \">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 56 ms\r\n\"\"\"\r\nclass Solution:\r\n  def topKFrequent(self, nums, k):\r\n    counts = collections.Counter(nums)\r\n    h = []\r\n    for num in counts.keys():\r\n      heapq.heappush(h, (counts[num], num))\r\n      if len(h) &gt; k: heapq.heappop(h)\r\n    return [heapq.heappop(h)[1] for i in range(k)]<\/pre>\n<\/div><\/div>\n<h1><strong>Solution 3: Bucket Sort<\/strong><\/h1>\n<p>Time complexity: O(n)<\/p>\n<p>Space complexity: O(n)<\/p>\n<div class=\"responsive-tabs\">\n<h2 class=\"tabtitle\">C++\/hashmap<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true \">class Solution {\r\npublic:\r\n    vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\r\n        unordered_map&lt;int, int&gt; count;\r\n        int max_freq = 1;\r\n        for (const int num : nums)\r\n            max_freq = max(max_freq, ++count[num]);\r\n        map&lt;int, vector&lt;int&gt;&gt; buckets;\r\n        for (const auto&amp; kv : count)\r\n            buckets[kv.second].push_back(kv.first);\r\n        vector&lt;int&gt; ans;\r\n        for (int i = max_freq; i &gt;= 1; --i) {\r\n            auto it = buckets.find(i);\r\n            if (it == buckets.end()) continue;\r\n            ans.insert(ans.end(), it-&gt;second.begin(), it-&gt;second.end());\r\n            if (ans.size() == k) return ans;\r\n        }\r\n        return ans;\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">C++\/array<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:c++ decode:true\">class Solution {\r\npublic:\r\n    vector&lt;int&gt; topKFrequent(vector&lt;int&gt;&amp; nums, int k) {\r\n        unordered_map&lt;int, int&gt; count;\r\n        for (const int num : nums)\r\n            ++count[num];\r\n        vector&lt;vector&lt;int&gt;&gt; buckets(nums.size() + 1);\r\n        for (const auto&amp; kv : count)\r\n            buckets[kv.second].push_back(kv.first);\r\n        vector&lt;int&gt; ans;\r\n        for (auto it = buckets.rbegin(); it != buckets.rend(); ++it) {\r\n            const vector&lt;int&gt;&amp; keys = *it;\r\n            if (keys.empty()) continue;\r\n            ans.insert(ans.begin(), keys.begin(), keys.end());\r\n            if (ans.size() == k) return ans;\r\n        }\r\n        return ans;\r\n    }\r\n};<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Java<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\/\/ Author: Huahua\r\n\/\/ Running time: 23 ms\r\nclass Solution {\r\n  public List&lt;Integer&gt; topKFrequent(int[] nums, int k) {\r\n    List[] buckets = new List[nums.length + 1];\r\n    Map&lt;Integer, Integer&gt; counts = new HashMap&lt;&gt;();\r\n\r\n    for (int num : nums)      \r\n      counts.put(num, counts.getOrDefault(num, 0) + 1);    \r\n        \r\n    for (int num : counts.keySet()) {\r\n      int count = counts.get(num);\r\n      if (buckets[count] == null)\r\n        buckets[count] = new ArrayList&lt;Integer&gt;();\r\n      buckets[count].add(num);\r\n    }\r\n    \r\n    List&lt;Integer&gt; ans = new ArrayList&lt;&gt;();\r\n    for (int i = buckets.length - 1; i &gt; 0 &amp;&amp; ans.size() &lt; k; --i) {\r\n      if (buckets[i] != null) ans.addAll(buckets[i]);      \r\n    }\r\n    return ans;    \r\n  }\r\n}<\/pre>\n\n<\/div><h2 class=\"tabtitle\">Python<\/h2>\n<div class=\"tabcontent\">\n\n<pre class=\"lang:default decode:true\">\"\"\"\r\nAuthor: Huahua\r\nRunning time: 64 ms\r\n\"\"\"\r\nclass Solution:\r\n  def topKFrequent(self, nums, k):\r\n    counts = collections.Counter(nums)\r\n    buckets = [[] for _ in range(len(nums) + 1)]    \r\n    for num in counts.keys():\r\n      buckets[counts[num]].append(num)\r\n    ans = []\r\n    for i in range(len(nums), 0, -1):      \r\n      ans += buckets[i]      \r\n      if len(ans) == k: return ans\r\n    return ans<\/pre>\n<\/div><\/div>\n<h1><strong>Related Problems<\/strong><\/h1>\n<ul>\n<li><a href=\"http:\/\/zxi.mytechroad.com\/blog\/heap\/leetcode-692-top-k-frequent-words\/\">[\u89e3\u9898\u62a5\u544a] LeetCode 692. Top K Frequent Words<\/a><\/li>\n<\/ul>\n","protected":false},"excerpt":{"rendered":"<p>Problem: 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&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[70,164],"tags":[138,24,177,72],"class_list":["post-669","post","type-post","status-publish","format-standard","hentry","category-hashtable","category-medium","tag-buckets","tag-frequency","tag-medium","tag-priority-queue","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/669","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/comments?post=669"}],"version-history":[{"count":15,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/669\/revisions"}],"predecessor-version":[{"id":3769,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/669\/revisions\/3769"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=669"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=669"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=669"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}