{"id":633,"date":"2021-02-12T14:44:12","date_gmt":"2021-02-12T06:44:12","guid":{"rendered":"http:\/\/lonelinerd.com\/?p=633"},"modified":"2021-02-17T14:40:54","modified_gmt":"2021-02-17T06:40:54","slug":"leetcode-350","status":"publish","type":"post","link":"https:\/\/lonelinerd.com\/index.php\/2021\/02\/12\/leetcode-350\/","title":{"rendered":"[LeetCode\u5237\u984c\u7b46\u8a18] 350 – Intersection of Two Arrays II"},"content":{"rendered":"\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t
\n\t\t\t
\n\t\t\t\t\t\t\t
\n\t\t\t\t\t\t
\n\t\t\t\t
\n\t\t\t\t\t\t\t\t
\n\t\t\t\t

\u984c\u76ee\u63cf\u8ff0\uff1a<\/strong><\/span><\/h4>

Given two arrays, write a function to compute their intersection.<\/span><\/p>

Example 1:<\/span><\/strong><\/span><\/p>

Input: nums1 = [1,2,2,1], nums2 = [2,2]<\/span>
Output: [2,2]<\/span><\/pre>
Example 2:<\/span><\/strong><\/span><\/p>
Input: nums1 = [4,9,5], nums2 = [9,4,9,8,4]<\/span>
Output: [4,9]<\/span><\/pre>
Note:<\/span><\/strong><\/span><\/p>
  • Each element in the result should appear as many times as it shows in both arrays.<\/span><\/p><\/li>
  • The result can be in any order.<\/span><\/p><\/li><\/ul>
    Follow up:<\/span><\/strong><\/span><\/p>
    • What if the given array is already sorted? How would you optimize your algorithm?<\/span><\/p><\/li>
    • What if <\/span>nums1<\/span><\/em><\/span>‘s size is small compared to <\/span>nums2<\/span><\/em><\/span>‘s size? Which algorithm is better?<\/span><\/p><\/li>
    • What if elements of <\/span>nums2<\/span><\/em><\/span> are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?<\/span><\/p><\/li><\/ul>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t
      \n\t\t\t\t
      \u4e00\u5237\u984c\u89e3\uff08Binary Search\uff09\uff1a<\/strong><\/span><\/h4>
      \u00a0 \u00a0 \u00a0 \u00a0 \u9019\u984c\u5728\u4f7f\u7528Binary Search\u6c42\u89e3\u6642\uff0c\u8207\u4e0a\u4e00\u984c\u300cIntersection Of Two Arrays\u300d\u662f\u4e00\u6a23\u7684\u3002\u53ea\u662f\u4e0a\u4e00\u984c\u5728\u628a\u5171\u540c\u7684\u5143\u7d20\u52a0\u5230\u7d50\u679c\u6578\u7d44\u6642\u8981\u78ba\u4fdd\u5143\u7d20\u7684\u552f\u4e00\u6027\uff0c\u800c\u9019\u4e00\u984c\u5c31\u4e0d\u9700\u8981\u4e86\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t
      \n\t\t\t\t
      public<\/span> class<\/span> Solution<\/span><\/span>
      {<\/span>
       \u00a0 \u00a0public<\/span> int<\/span>[] Intersect<\/span>(int<\/span>[] nums1<\/span>, int<\/span>[] nums2<\/span>)<\/span>
       \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0List<\/span><<\/span>int<\/span>><\/span> nums1Copy<\/span> =<\/span> nums1<\/span>.ToList<\/span>();<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0List<\/span><<\/span>int<\/span>><\/span> nums2Copy<\/span> =<\/span> nums2<\/span>.ToList<\/span>();<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0List<\/span><<\/span>int<\/span>><\/span> resList<\/span> =<\/span> new<\/span> List<\/span><<\/span>int<\/span>><\/span>();<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0bool<\/span> isNums1Longer<\/span> =<\/span> nums1Copy<\/span>.Count<\/span> ><\/span> nums2Copy<\/span>.Count<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(isNums1Longer<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0nums1Copy<\/span>.Sort<\/span>();<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0else<\/span><\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0nums2Copy<\/span>.Sort<\/span>();<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span>(int<\/span> i<\/span> in<\/span> isNums1Longer<\/span> ?<\/span> nums2Copy<\/span> : nums1Copy<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(BS<\/span>(isNums1Longer<\/span> ?<\/span> nums1Copy<\/span> : nums2Copy<\/span>, i<\/span>))<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0resList<\/span>.Add<\/span>(i<\/span>);<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0return<\/span> resList<\/span>.ToArray<\/span>();<\/span>
       \u00a0  }<\/span>
       \u00a0 \u00a0bool<\/span> BS<\/span>(int<\/span>[] nums<\/span>, int<\/span> val<\/span>)<\/span>
       \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0int<\/span> left<\/span> =<\/span> 0<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0int<\/span> right<\/span> =<\/span> nums<\/span>.Count<\/span> -<\/span> 1<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0int<\/span> mid<\/span> =<\/span> 0<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0while<\/span>(left<\/span> <=<\/span> right<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0mid<\/span> =<\/span> left<\/span> +<\/span> (right<\/span> -<\/span> left<\/span>) \/<\/span> 2<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span>(nums<\/span>[mid<\/span>] ==<\/span> val<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0nums<\/span>.RemoveAt<\/span>(mid<\/span>);<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0return<\/span> true<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0else<\/span> if<\/span>(nums<\/span>[mid<\/span>] ><\/span> val<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0right<\/span> =<\/span> mid<\/span> -<\/span> 1<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0else<\/span><\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0left<\/span> =<\/span> mid<\/span> +<\/span> 1<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0return<\/span> false<\/span>;<\/span>
       \u00a0  }<\/span>
      }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t
      \n\t\t\t\t
      \u4e8c\u5237\u984c\u89e3\uff08Dictionary\uff09\uff1a<\/strong><\/span><\/h4>
      \u00a0 \u00a0 \u00a0 \u00a0 \u9019\u4e00\u984c\u9664\u4e86Binary Search\u4ee5\u5916\uff0c\u4e5f\u53ef\u4ee5\u7528\u6548\u7387\u66f4\u9ad8\u7684Dictionary\u6c42\u89e3\u3002\u9996\u5148\u628a\u5176\u4e2d\u4e00\u500b\u6578\u7d44\uff08arr1\uff09\u7684\u5143\u7d20\u4f5c\u70ba\u9375\uff0c\u4ee5\u53ca\u9019\u500b\u5143\u7d20\u5728\u6578\u7d44\u88e1\u7684\u51fa\u73fe\u6b21\u6578\u4f5c\u70ba\u503c\u52a0\u5230\u5b57\u5178\u88e1\u3002\u7136\u5f8c\u518d\u904d\u6b77\u53e6\u4e00\u500b\u6578\u7d44\uff08arr2\uff09\uff0c\u6aa2\u67e5\u5b57\u5178\u4e2d\u662f\u5426\u5305\u542b\u88e1\u9762\u7684\u5143\u7d20\uff0c\u5982\u679c\u662f\u7684\u8a71\uff0c\u5c31\u5c07\u5b57\u5178\u88e1\u8a72\u5143\u7d20\u7684\u503c\uff08arr1\u4e2d\u8a72\u5143\u7d20\u7684\u51fa\u73fe\u6b21\u6578\uff09-1\uff0c\u4e26\u5c07\u5143\u7d20\u52a0\u5230\u7d50\u679c\u6578\u7d44\u4e2d\u3002<\/p>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t\t\t\t
      \n\t\t\t\t
      public<\/span> class<\/span> Solution<\/span> {<\/span>
       \u00a0 \u00a0public<\/span> int<\/span>[] Intersect<\/span>(int<\/span>[] nums1<\/span>, int<\/span>[] nums2<\/span>) {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0List<\/span><<\/span>int<\/span>><\/span> res<\/span> =<\/span> new<\/span> List<\/span><<\/span>int<\/span>><\/span>();<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0\/\/Key : number ; Value : Count<\/span><\/span>
       \u00a0 \u00a0 \u00a0 \u00a0Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span> numCnt<\/span> =<\/span> new<\/span> Dictionary<\/span><<\/span>int<\/span>, int<\/span>><\/span>();<\/span>
      \u200b<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0for<\/span> (int<\/span> i<\/span> =<\/span> 0<\/span>; i<\/span> <<\/span> nums1<\/span>.Length<\/span>; i<\/span>++<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span> (!<\/span>numCnt<\/span>.ContainsKey<\/span>(nums1<\/span>[i<\/span>]))<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0numCnt<\/span>.Add<\/span>(nums1<\/span>[i<\/span>], 1<\/span>);<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0else<\/span><\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0numCnt<\/span>[nums1<\/span>[i<\/span>]]++<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
      \u200b<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0foreach<\/span> (int<\/span> i<\/span> in<\/span> nums2<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0if<\/span> (numCnt<\/span>.ContainsKey<\/span>(i<\/span>) &&<\/span> numCnt<\/span>[i<\/span>] ><\/span> 0<\/span>)<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  {<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0res<\/span>.Add<\/span>(i<\/span>);<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0numCnt<\/span>[i<\/span>]--<\/span>;<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0  }<\/span>
       \u00a0 \u00a0 \u00a0 \u00a0return<\/span> res<\/span>.ToArray<\/span>();<\/span>
       \u00a0  }<\/span>
      }<\/span><\/pre>\t\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t
      \n\t\t\t\t\t\t\t
      \n\t\t\t\t\t\t
      \n\t\t\t\t
      \n\t\t\t\t\t
      \n\t\t\t\n\t\t\t\t\t\t<\/span>\n\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t<\/div>\n\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/div>\n\t\t\t\t\t\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t<\/section>\n\t\t\t\t\t\t\t\t\t<\/div>\n\t\t\t<\/div>\n\t\t\t\t\t<\/div>\n\t\t","protected":false},"excerpt":{"rendered":"
      \u984c\u76ee\u63cf\u8ff0\uff1a Given two arrays, write a function to compute the …<\/p>\n
        [LeetCode\u5237\u984c\u7b46\u8a18] 350 – Intersection of Two Arrays II<\/span> Read More »<\/a><\/p>\n","protected":false},"author":1,"featured_media":570,"comment_status":"closed","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[4,16],"tags":[],"class_list":["post-633","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-programming-notes","category-leetcodes"],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"https:\/\/lonelinerd.com\/wp-content\/uploads\/2021\/02\/FeatureCover_LeetCoding.png","_links":{"self":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/633","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/comments?post=633"}],"version-history":[{"count":14,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/633\/revisions"}],"predecessor-version":[{"id":649,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/posts\/633\/revisions\/649"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media\/570"}],"wp:attachment":[{"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/media?parent=633"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/categories?post=633"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/lonelinerd.com\/index.php\/wp-json\/wp\/v2\/tags?post=633"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}