{"id":4420,"date":"2018-12-09T01:49:00","date_gmt":"2018-12-09T09:49:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=4420"},"modified":"2018-12-09T01:49:09","modified_gmt":"2018-12-09T09:49:09","slug":"leetcode-954-array-of-doubled-pairs","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/hashtable\/leetcode-954-array-of-doubled-pairs\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 954. Array of Doubled Pairs"},"content":{"rendered":"

Problem<\/strong><\/h1>\n

Given an array of integers\u00a0A<\/code>\u00a0with even length, return\u00a0true<\/code>\u00a0if and only if it is possible to reorder it such that\u00a0A[2 * i + 1] = 2 * A[2 * i]<\/code>\u00a0for every\u00a00 <=\u00a0i < len(A) \/ 2<\/code>.<\/p>\n

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

Input: <\/strong>[3,1,3,6]<\/span>\r\nOutput: <\/strong>false<\/span>\r\n<\/pre>\n
Example 2:<\/strong><\/p>\n
Input: <\/strong>[2,1,2,6]<\/span>\r\nOutput: <\/strong>false<\/span>\r\n<\/pre>\n
Example 3:<\/strong><\/p>\n
Input: <\/strong>[4,-2,2,-4]<\/span>\r\nOutput: <\/strong>true<\/span>\r\nExplanation: <\/strong>We can take two groups, [-2,-4] and [2,4] to form [-2,-4,2,4] or [2,4,-2,-4].<\/span>\r\n<\/pre>\n
Example 4:<\/strong><\/p>\n
Input: <\/strong>[1,2,4,16,8,4]<\/span>\r\nOutput: <\/strong>false<\/span>\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 0 <= A.length <= 30000<\/code><\/li>\n
  2. A.length<\/code>\u00a0is even<\/li>\n
  3. -100000 <= A[i] <= 100000<\/code><\/li>\n<\/ol>\n
    Solution 1:<\/strong><\/h1>\n
    Time complexity: O(N +\u00a0100000 * 2)<\/p>\n
    Space complexity: O(100000 * 2)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 108 ms\r\nclass Solution {\r\npublic:\r\n  bool canReorderDoubled(vector<int>& A) {\r\n    const int kMaxN = 100000;\r\n    vector<int> p(kMaxN + 1);\r\n    vector<int> n(kMaxN + 1);\r\n    for (int a : A) {\r\n      if (a >= 0) ++p[a];\r\n      else ++n[-a];\r\n    }\r\n    for (int i = 0; i <= kMaxN \/ 2; ++i) {\r\n      if (p[i] && (p[i * 2] -= p[i]) < 0) return false;      \r\n      if (n[i] && (n[i * 2] -= n[i]) < 0) return false;      \r\n    }\r\n    return true;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
    Solution 2:<\/strong><\/h1>\n
    Time complexity: O(NlogN)<\/p>\n
    Space complexity: O(N)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 108 ms\r\nclass Solution {\r\npublic:\r\n  bool canReorderDoubled(vector<int>& A) {\r\n    unordered_map<int, int> c;\r\n    for (int a : A) ++c[a];\r\n    vector<int> keys;\r\n    for (const auto &kv : c) keys.push_back(kv.first);\r\n    sort(begin(keys), end(keys), [](int a, int b) { return abs(a) < abs(b); });\r\n    for (int key : keys)\r\n      if (c[key] && (c[key * 2] -= c[key]) < 0) return false;\r\n    return true;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n
     <\/p>\n
     <\/p>\n","protected":false},"excerpt":{"rendered":"
    Problem Given an array of integers\u00a0A\u00a0with even length, return\u00a0true\u00a0if and only if it is possible to reorder it such that\u00a0A[2 * i + 1] =…<\/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":[82,31,177,15],"class_list":["post-4420","post","type-post","status-publish","format-standard","hentry","category-hashtable","tag-hashtable","tag-math","tag-medium","tag-sorting","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4420","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=4420"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4420\/revisions"}],"predecessor-version":[{"id":4422,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/4420\/revisions\/4422"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=4420"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=4420"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=4420"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}