{"id":3550,"date":"2018-08-16T09:14:30","date_gmt":"2018-08-16T16:14:30","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3550"},"modified":"2018-08-16T09:21:57","modified_gmt":"2018-08-16T16:21:57","slug":"leetcode-561-array-partition-i","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-561-array-partition-i\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 561. Array Partition I"},"content":{"rendered":"<p><iframe loading=\"lazy\" title=\"\u82b1\u82b1\u9171 LeetCode 561. Array Partition I - \u5237\u9898\u627e\u5de5\u4f5c EP8\" width=\"500\" height=\"375\" src=\"https:\/\/www.youtube.com\/embed\/wDU72F6dhS4?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<h1>Problem<\/h1>\n<p>Given an array of\u00a0<b>2n<\/b>\u00a0integers, your task is to group these integers into\u00a0<b>n<\/b>\u00a0pairs of integer, say (a<sub>1<\/sub>, b<sub>1<\/sub>), (a<sub>2<\/sub>, b<sub>2<\/sub>), &#8230;, (a<sub>n<\/sub>, b<sub>n<\/sub>) which makes sum of min(a<sub>i<\/sub>, b<sub>i<\/sub>) for all i from 1 to n as large as possible.<\/p>\n<p><b>Example 1:<\/b><\/p>\n<pre class=\"crayon:false\"><b>Input:<\/b> [1,4,3,2]\r\n\r\n<b>Output:<\/b> 4\r\n<b>Explanation:<\/b> n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).\r\n<\/pre>\n<p><b>Note:<\/b><\/p>\n<ol>\n<li><b>n<\/b>\u00a0is a positive integer, which is in the range of [1, 10000].<\/li>\n<li>All the integers in the array will be in the range of [-10000, 10000].<\/li>\n<\/ol>\n<h1><strong>Solution 1: Sorting<\/strong><\/h1>\n<p>Time complexity: O(nlogn)<\/p>\n<p>Space complexity: O(1)<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 52 ms\r\nclass Solution {\r\npublic:\r\n  int arrayPairSum(vector&lt;int&gt;&amp; nums) {\r\n    std::sort(nums.begin(), nums.end());\r\n    int ans = 0;\r\n    for(int i = 0; i &lt; nums.size(); i += 2)\r\n        ans += nums[i];\r\n    return ans;\r\n  }\r\n};<\/pre>\n<h1><strong>Solution 2: HashTable<\/strong><\/h1>\n<p>Time complexity: O(n + max(nums) &#8211; min(nums))<\/p>\n<p>Space complexity: O(max(nums) &#8211; min(nums))<\/p>\n<pre class=\"lang:default decode:true \">\/\/ Author: Huahua\r\n\/\/ Running time: 39 ms\r\nclass Solution {\r\npublic:\r\n  int arrayPairSum(vector&lt;int&gt;&amp; nums) {\r\n    const int max_val = *max_element(begin(nums), end(nums));\r\n    const int min_val = *min_element(begin(nums), end(nums));\r\n    const int offset = -min_val;\r\n    vector&lt;int&gt; c(max_val - min_val + 1);\r\n\r\n    for (int num : nums)\r\n        ++c[num + offset];\r\n\r\n    int ans = 0;\r\n    int index = 0;\r\n\r\n    int n = min_val;\r\n\r\n    while (n &lt;= max_val) {\r\n      if (c[n + offset] == 0) {\r\n        ++n;\r\n        continue;\r\n      }\r\n      ans += (++index &amp; 1) ? n : 0;\r\n      --c[n + offset];\r\n    }\r\n    return ans;\r\n  }\r\n};<\/pre>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Problem Given an array of\u00a02n\u00a0integers, your task is to group these integers into\u00a0n\u00a0pairs of integer, say (a1, b1), (a2, b2), &#8230;, (an, bn) which makes&#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],"tags":[20,222,150],"class_list":["post-3550","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-array","tag-easy","tag-partition","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3550","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=3550"}],"version-history":[{"count":4,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3550\/revisions"}],"predecessor-version":[{"id":3554,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3550\/revisions\/3554"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3550"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3550"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3550"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}