{"id":2037,"date":"2018-03-08T08:20:07","date_gmt":"2018-03-08T16:20:07","guid":{"rendered":"http:\/\/zxi.mytechroad.com\/blog\/?p=2037"},"modified":"2018-03-08T08:22:24","modified_gmt":"2018-03-08T16:22:24","slug":"leetcode-349-intersection-of-two-arrays","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-349-intersection-of-two-arrays\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 349. Intersection of Two Arrays"},"content":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u6c422\u4e2a\u6570\u7ec4\u7684\u4ea4\u96c6\u3002<\/p>\n<p><strong>Problem:<\/strong><\/p>\n<p><a href=\"https:\/\/leetcode.com\/problems\/intersection-of-two-arrays\/description\/\">https:\/\/leetcode.com\/problems\/intersection-of-two-arrays\/description\/<\/a><\/p>\n<p>Given two arrays, write a function to compute their intersection.<\/p>\n<p><b>Example:<\/b><br \/>\nGiven\u00a0<i>nums1<\/i>\u00a0=\u00a0<code>[1, 2, 2, 1]<\/code>,\u00a0<i>nums2<\/i>\u00a0=\u00a0<code>[2, 2]<\/code>, return\u00a0<code>[2]<\/code>.<\/p>\n<p><b>Note:<\/b><\/p>\n<ul>\n<li>Each element in the result must be unique.<\/li>\n<li>The result can be in any order.<\/li>\n<\/ul>\n<p>C++ using std::set_intersection<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 8 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; intersection(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2) {\r\n    vector&lt;int&gt; intersection(max(nums1.size(), nums2.size()));\r\n    std::sort(nums1.begin(), nums1.end());\r\n    std::sort(nums2.begin(), nums2.end());\r\n    \/\/ Inputs must be in ascending order\r\n    auto it = std::set_intersection(nums1.begin(), nums1.end(), nums2.begin(), nums2.end(), intersection.begin());\r\n    intersection.resize(it - intersection.begin());\r\n    std::set&lt;int&gt; s(intersection.begin(), intersection.end());\r\n    return vector&lt;int&gt;(s.begin(), s.end());\r\n  }\r\n};<\/pre>\n<p>C++ hashtable<\/p>\n<pre class=\"lang:c++ decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 7 ms\r\nclass Solution {\r\npublic:\r\n  vector&lt;int&gt; intersection(vector&lt;int&gt;&amp; nums1, vector&lt;int&gt;&amp; nums2) {\r\n    unordered_set&lt;int&gt; m(nums1.begin(), nums1.end());\r\n    vector&lt;int&gt; ans;\r\n    for (int num : nums2) {\r\n      if (!m.count(num)) continue;\r\n      ans.push_back(num);\r\n      m.erase(num);\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u5927\u610f\uff1a\u6c422\u4e2a\u6570\u7ec4\u7684\u4ea4\u96c6\u3002 Problem: https:\/\/leetcode.com\/problems\/intersection-of-two-arrays\/description\/ Given two arrays, write a function to compute their intersection. Example: Given\u00a0nums1\u00a0=\u00a0[1, 2, 2, 1],\u00a0nums2\u00a0=\u00a0[2, 2], return\u00a0[2]. Note: Each element in the&#8230;<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184,70],"tags":[210,243,15,240],"class_list":["post-2037","post","type-post","status-publish","format-standard","hentry","category-array","category-hashtable","tag-intersection","tag-set","tag-sorting","tag-unique","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2037","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=2037"}],"version-history":[{"count":3,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2037\/revisions"}],"predecessor-version":[{"id":2040,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/2037\/revisions\/2040"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=2037"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=2037"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=2037"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}