{"id":1795,"date":"2016-02-10T17:15:12","date_gmt":"2016-02-10T09:15:12","guid":{"rendered":"http:\/\/boweihe.me\/?p=1795"},"modified":"2016-02-10T17:15:12","modified_gmt":"2016-02-10T09:15:12","slug":"leetcode-4-median-of-two-sorted-arrays","status":"publish","type":"post","link":"https:\/\/dayandcarrot.space\/?p=1795","title":{"rendered":"LeetCode #4. Median of Two Sorted Arrays"},"content":{"rendered":"<p><strong>\u9898\u76ee\u94fe\u63a5<\/strong>\uff1a<a href=\"https:\/\/leetcode.com\/problems\/median-of-two-sorted-arrays\/\" target=\"_blank\" rel=\"noopener noreferrer\">https:\/\/leetcode.com\/problems\/median-of-two-sorted-arrays\/<\/a><br \/>\n<strong>\u53c2\u8003\u6587\u732e<\/strong>\uff1a<\/p>\n<ul>\n<li><a href=\"http:\/\/www.acmerblog.com\/median-of-two-sorted-arrays-5967.html\" target=\"_blank\" rel=\"noopener noreferrer\">\u6c42\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u7684\u4e2d\u4f4d\u6570-\u7b97\u6cd5\u5bfc\u8bba<\/a><\/li>\n<li><a href=\"http:\/\/www.cnblogs.com\/TenosDoIt\/p\/3554479.html\" target=\"_blank\" rel=\"noopener noreferrer\">\u6c42\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u7684\u4e2d\u4f4d\u6570\u6216\u8005\u7b2ck\u5c0f\u5143\u7d20<\/a><\/li>\n<\/ul>\n<p><strong>\u601d\u8def\uff1a<\/strong><br \/>\n\u5b9e\u5728\u662f\u8111\u5b50\u8f6c\u4e0d\u8fc7\u6765\uff0c\u770b\u4e86\u4e00\u4e0b\u89e3\u6cd5\uff0c\u7136\u540e\u5c31\u628a\u81ea\u5df1\u7684\u7406\u89e3\u8bb2\u4e00\u4e0b\u5427\u3002<br \/>\n\u6709\u4e24\u4e2a<em>\u89c4\u5f8b<\/em>\u9700\u8981\u8bf4\u4e0b\uff1a<br \/>\n1.\u5728\u67d0\u4e2a\u6570\u5217\u5934\u5c3e\u5220\u53bb\u76f8\u540c\u6570\u91cf\u7684\u5143\u7d20\uff0c\u5176\u4e2d\u4f4d\u6570\u662f\u4e0d\u53d8\u7684\u3002\u6bd4\u5982[1,2,3,4]\u5220\u53bb1\u548c4.<br \/>\n2.\u5982\u679c\u4e24\u4e2a\u6570\u5217\u7684\u4e2d\u4f4d\u6570\u662fm1, m2\uff0c\u90a3\u4e48\u5408\u5e76\u540e\u7684\u6570\u5217\u7684\u4e2d\u4f4d\u6570\u7684\u503c\u80af\u5b9a\u5728[m1,m2]\u8303\u56f4\u5185\u3002<br \/>\n\u65e2\u7136\u9898\u76ee\u662f\u8981Log\u7ea7\u522b\u7684\u590d\u6742\u5ea6\uff0c\u5c31\u8981\u60f3\u5230\u8981\u7528\u6298\u534a\u6cd5\u628a\u95ee\u9898\u7684\u89c4\u6a21\u964d\u4f4e&#8230;\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5047\u8bbe\u6709[1,2,4,6,6,8]\u548c[1,5,7,8,10,25,36]\u4e24\u4e2a\u6570\u5217\uff0c\u5f88\u5bb9\u6613\u7b97\u51fa\u4ed6\u4eec\u7684\uff08\u524d\u5e8f \uff09\u4e2d\u4f4d\u6570\u5206\u522b\u662f4\u548c8\uff0c\u800c\u4ed6\u4eec\u5408\u5e76\u540e\u7684\u4e2d\u4f4d\u6570\u7684\u503c\u5728[4,8]\u4e4b\u95f4\u3002<br \/>\n\u7136\u540e\u53ef\u4ee5\u5220\u53bb\u65e0\u7528\u7684\u503c\uff0c[1,2]\u4e0e[10,25,36]. \u4f46\u7531\u4e8e\u89c4\u5f8b1\u7684\u9650\u5236\uff0c\u5982\u679c\u540e\u9762\u5220\u4e863\u4e2a\u7684\u8bdd\uff0c\u5408\u5e76\u540e\u5220\u51cf\u7684\u6570\u5217\u4f1a\u53d1\u751f\u53d8\u5316\uff08\u672c\u4f8b\u4e2d\u5947\u5076\u6027\u90fd\u53d8\u4e86\uff09\uff0c\u6211\u4eec\u53ea\u80fd\u5220\u53bbmin(2,3)=2\u4e2a\u5143\u7d20&#8230;\u8fd9\u79cd\u5220\u503c\u4ece\u7406\u8bba\u4e0a\u8bb2\u5c31\u662f<strong>\u6298\u534a<\/strong>\u4e86\uff0c\u7136\u540e\u641e\u4e00\u6ce2\u9012\u5f52\u5c31\u884c\u4e86\u3002<br \/>\n\u6700\u6700\u6700\u57fa\u672c\u7684\u601d\u8def\u5982\u4e0b\uff1a<\/p>\n<pre class=\"lang:default decode:true\">\u4e24\u4e2a\u6709\u5e8f\u6570\u5217Ary1, Ary2\uff08\u5047\u8bbe\u5347\u5e8f\u6392\u5217\uff09\u7684\u4e2d\u4f4d\u6570\u5206\u522b\u4e3am1,m2\nif m1 == m2:\n    LUCKY!!!\nelif m1 &lt; m2:\n    \u53d6\uff08Ary1\u7684\u540e\u534a\u6bb5\uff0cAry2\u7684\u524d\u534a\u6bb5\uff09\u518d\u7b97\nelse\n    \u53d6\uff08Ary1\u7684\u524d\u534a\u6bb5\uff0cAry2\u7684\u540e\u534a\u6bb5\uff09\u518d\u7b97<\/pre>\n<p>\u7531\u4e8e\u9898\u8bbe\u91cc\u9762\u4fe9\u6570\u7ec4\u662f\u4e0d\u7b49\u957f\u7684\uff0c\u6240\u4ee5\u91cc\u5bf9\u5176\u4e2d\u67d0\u4e2a\u6570\u7ec4n&lt;=2\u65f6\u5904\u7406\u65b9\u6cd5\u9700\u8981\u6ce8\u610f&#8230;<br \/>\n<strong>\u4ee3\u7801\uff1a<\/strong><\/p>\n<pre class=\"lang:c decode:true \">int max(int x, int y) {\n    return x&gt;y ? x : y;\n}\nint min(int x, int y) {\n    return x&lt;y ? x : y;\n}\ndouble getMedian(int* nums, int size) {\n\tif (size == 0)\n\t\treturn -1;\n\tif (size % 2 == 0) {\n\t\t\/\/Even number\n\t\treturn (nums[size \/ 2] + nums[size \/ 2 - 1]) \/ 2.0;\n\t}\n\telse {\n\t\treturn nums[(size - 1) \/ 2];\n\t}\n}\ndouble findMedianMerge(int* nums1, int nums1Size, int* nums2, int nums2Size) {\n\tint count = 0;\n\tint n1Count = 0;\n\tint totalSize = nums1Size + nums2Size;\n\tint t1, t2;\n\tif (totalSize % 2 == 0) {\n\t\tt1 = totalSize \/ 2;\n\t\tt2 = t1 + 1;\n\t}\n\telse {\n\t\tt1 = -1;\n\t\tt2 = totalSize \/ 2 + 1;\n\t}\n\tdouble sum = 0;\n\tint curVal;\n\twhile (n1Count &lt; nums1Size) {\n\t\tif (*nums1 &lt; *nums2) {\n\t\t\tn1Count++;\n\t\t\tcurVal = *nums1;\n\t\t\tnums1++;\n\t\t}\n\t\telse {\n\t\t\tcurVal = *nums2;\n\t\t\tnums2++;\n\t\t}\n\t\tcount++;\n\t\tif (count == t1 || count == t2) {\n\t\t\tsum += curVal;\n\t\t}\n\t\telse if (count &gt;= t2) {\n\t\t\tbreak;\n\t\t}\n\t}\n\tif (count &lt; t1) {\n\t\t\/\/Not finished\n\t\tnums2 += (t1 - count - 1);\n\t\tcount = t1;\n\t\tsum += *nums2;\n\t\tnums2++;\n\t}\n\tif (count &lt; t2) {\n\t\tnums2 += (t2 - count - 1);\n\t\tsum += *nums2;\n\t}\n\tif (t1 == -1)\n\t\treturn sum;\n\telse\n\t\treturn sum \/ 2.0;\n}\ndouble findMedianSortedArrays(int* nums1, int nums1Size, int* nums2, int nums2Size) {\n\tint totalSize = nums1Size + nums2Size;\n\tif (nums1Size &gt; nums2Size) {\n\t\t\/\/Keep ary1 shorter than ary2\n\t\tint* temp = nums1;\n\t\tint t = nums1Size;\n\t\tnums1 = nums2;\n\t\tnums1Size = nums2Size;\n\t\tnums2 = temp;\n\t\tnums2Size = t;\n\t}\n\tif (nums1Size == 0) {\n\t\treturn getMedian(nums2, nums2Size);\n\t} else if (nums1Size == 1) {\n\t\tif (nums2Size == 1) {\n\t\t\treturn (nums1[0] + nums2[0]) \/ 2.0;\n\t\t}\n\t\telse {\n\t\t\treturn findMedianMerge(nums1, nums1Size, nums2, nums2Size);\n\t\t}\n\t}\n\telse if (nums1Size == 2) {\n\t\tif (nums2Size == 2) {\n\t\t\treturn (max(nums1[0], nums2[0]) + min(nums1[1], nums2[1])) \/ 2.0;\n\t\t}\n\t\telse {\n\t\t\treturn findMedianMerge(nums1, nums1Size, nums2, nums2Size);\n\t\t}\n\t}\n\t\/\/Slice\n\tdouble m1 = getMedian(nums1, nums1Size);\n\tdouble m2 = getMedian(nums2, nums2Size);\n\tif (m1 == m2) {\n\t\t\/\/Got lucky\n\t\treturn m1;\n\t}\n\telse if (m1 &lt; m2) {\n\t\t\/\/Slice L-nums1 and R-nums2\n\t\tint cut = (nums1Size - 1) \/ 2;\n\t\treturn findMedianSortedArrays(nums1 + cut, nums1Size - cut, nums2, nums2Size - cut);\n\t}\n\telse {\n\t\t\/\/Slice R-nums1 and L-nums2\n\t\tint cut = (nums1Size - 1) \/ 2;\n\t\treturn findMedianSortedArrays(nums1, nums1Size - cut, nums2 + cut, nums2Size - cut);\n\t}\n}<\/pre>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>\u9898\u76ee\u94fe\u63a5\uff1ahttps:\/\/leetcode.com\/problems\/median-of-two-sorted-arrays\/ \u53c2\u8003\u6587\u732e\uff1a \u6c42\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u7684\u4e2d\u4f4d\u6570-\u7b97\u6cd5\u5bfc\u8bba \u6c42\u4e24\u4e2a\u6709\u5e8f\u6570\u7ec4\u7684\u4e2d\u4f4d\u6570\u6216\u8005\u7b2ck\u5c0f\u5143\u7d20 \u601d\u8def\uff1a \u5b9e\u5728\u662f\u8111\u5b50\u8f6c\u4e0d\u8fc7\u6765\uff0c\u770b\u4e86\u4e00\u4e0b\u89e3\u6cd5\uff0c\u7136\u540e\u5c31\u628a\u81ea\u5df1\u7684\u7406\u89e3\u8bb2\u4e00\u4e0b\u5427\u3002 \u6709\u4e24\u4e2a\u89c4\u5f8b\u9700\u8981\u8bf4\u4e0b\uff1a 1.\u5728\u67d0\u4e2a\u6570\u5217\u5934\u5c3e\u5220\u53bb\u76f8\u540c\u6570\u91cf\u7684\u5143\u7d20\uff0c\u5176\u4e2d\u4f4d\u6570\u662f\u4e0d\u53d8\u7684\u3002\u6bd4\u5982[1,2,3,4]\u5220\u53bb1\u548c4. 2.\u5982\u679c\u4e24\u4e2a\u6570\u5217\u7684\u4e2d\u4f4d\u6570\u662fm1, m2\uff0c\u90a3\u4e48\u5408\u5e76\u540e\u7684\u6570\u5217\u7684\u4e2d\u4f4d\u6570\u7684\u503c\u80af\u5b9a\u5728[m1,m2]\u8303\u56f4\u5185\u3002 \u65e2\u7136\u9898\u76ee\u662f\u8981Log\u7ea7\u522b\u7684\u590d\u6742\u5ea6\uff0c\u5c31\u8981\u60f3\u5230\u8981\u7528\u6298\u534a\u6cd5\u628a\u95ee\u9898\u7684\u89c4\u6a21\u964d\u4f4e&#8230;\u4e3e\u4e2a\u4f8b\u5b50\uff0c\u5047\u8bbe\u6709[1,2,4,6,6,8]\u548c[1,5,7,8,10,25,36]\u4e24\u4e2a\u6570\u5217\uff0c\u5f88\u5bb9\u6613\u7b97\u51fa\u4ed6\u4eec\u7684\uff08\u524d\u5e8f \uff09\u4e2d\u4f4d\u6570\u5206\u522b\u662f4\u548c8\uff0c\u800c\u4ed6\u4eec\u5408\u5e76\u540e\u7684\u4e2d\u4f4d\u6570\u7684\u503c\u5728[4,8]\u4e4b\u95f4\u3002 \u7136\u540e\u53ef\u4ee5\u5220\u53bb\u65e0\u7528\u7684\u503c\uff0c[1,2]\u4e0e[10,25,36]. \u4f46\u7531\u4e8e\u89c4\u5f8b1\u7684\u9650\u5236\uff0c\u5982\u679c\u540e\u9762\u5220\u4e863\u4e2a\u7684\u8bdd\uff0c\u5408\u5e76\u540e\u5220\u51cf\u7684\u6570\u5217\u4f1a\u53d1\u751f\u53d8\u5316\uff08\u672c\u4f8b\u4e2d\u5947\u5076\u6027\u90fd\u53d8\u4e86\uff09\uff0c\u6211\u4eec\u53ea\u80fd\u5220\u53bbmin(2,3)=2\u4e2a\u5143\u7d20&#8230;\u8fd9\u79cd\u5220\u503c\u4ece\u7406\u8bba\u4e0a\u8bb2\u5c31\u662f\u6298\u534a\u4e86\uff0c\u7136\u540e\u641e\u4e00\u6ce2\u9012\u5f52\u5c31\u884c\u4e86\u3002 \u6700\u6700\u6700\u57fa\u672c\u7684\u601d\u8def\u5982\u4e0b\uff1a \u4e24\u4e2a\u6709\u5e8f\u6570\u5217Ary1, Ary2\uff08\u5047\u8bbe\u5347\u5e8f\u6392\u5217\uff09\u7684\u4e2d\u4f4d\u6570\u5206\u522b\u4e3am1,m2 if m1 == m2: LUCKY!!! elif m1 &lt; m2: \u53d6\uff08Ary1\u7684\u540e\u534a\u6bb5\uff0cAry2\u7684\u524d\u534a\u6bb5\uff09\u518d\u7b97 else \u53d6\uff08Ary1\u7684\u524d\u534a\u6bb5\uff0cAry2\u7684\u540e\u534a\u6bb5\uff09\u518d\u7b97 \u7531\u4e8e\u9898\u8bbe\u91cc\u9762\u4fe9\u6570\u7ec4\u662f\u4e0d\u7b49\u957f\u7684\uff0c\u6240\u4ee5\u91cc\u5bf9\u5176\u4e2d\u67d0\u4e2a\u6570\u7ec4n&lt;=2\u65f6\u5904\u7406\u65b9\u6cd5\u9700\u8981\u6ce8\u610f&#8230; \u4ee3\u7801\uff1a int max(int x, int y) { return x&gt;y ? x : y; } int min(int x, int y) { return x&lt;y ? x : [&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,185],"class_list":["post-1795","post","type-post","status-publish","format-standard","hentry","category-study","tag-leetcode-oj","tag-185"],"_links":{"self":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1795","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=1795"}],"version-history":[{"count":0,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=\/wp\/v2\/posts\/1795\/revisions"}],"wp:attachment":[{"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=1795"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=1795"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/dayandcarrot.space\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=1795"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}