{"id":3984,"date":"2018-09-15T20:32:00","date_gmt":"2018-09-16T03:32:00","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=3984"},"modified":"2018-09-15T20:32:14","modified_gmt":"2018-09-16T03:32:14","slug":"leetcode-905-sort-array-by-parity","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/algorithms\/array\/leetcode-905-sort-array-by-parity\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 905. Sort Array By Parity"},"content":{"rendered":"

Problem<\/h1>\n

Given an array\u00a0A<\/code>\u00a0of non-negative integers, return an array consisting of all the even elements of\u00a0A<\/code>, followed by all the odd elements of\u00a0A<\/code>.<\/p>\n

You may return any answer array that satisfies this condition.<\/p>\n

\n

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

Input: <\/strong>[3,1,2,4]<\/span>\r\nOutput: <\/strong>[2,4,3,1]<\/span>\r\nThe outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.\r\n<\/pre>\n
Note:<\/strong><\/p>\n
    \n
  1. 1 <= A.length <= 5000<\/code><\/li>\n
  2. 0 <= A[i] <= 5000<\/code><\/li>\n<\/ol>\n
    Solution 1: Split Odd\/Even<\/strong><\/h1>\n
    Time complexity: O(n)<\/p>\n
    Space complexity: O(n)<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 44 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> sortArrayByParity(vector<int>& A) {\r\n    vector<int> even;\r\n    vector<int> odd;\r\n    for (int a : A) {\r\n      if (a % 2) odd.push_back(a);\r\n      else even.push_back(a);\r\n    }\r\n    even.insert(end(even), begin(odd), end(odd));\r\n    return even;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n<\/div>\n
    Solution 2: Stable sort by key % 2<\/strong><\/h1>\n
    Time complexity: O(nlogn)<\/p>\n
    Space complexity: O(1) in-place<\/p>\n
    \n
    C++<\/h2>\n
    \n\n
    \/\/ Author: Huahua, 52 ms\r\nclass Solution {\r\npublic:\r\n  vector<int> sortArrayByParity(vector<int>& A) {\r\n    stable_sort(begin(A), end(A), [](int a, int b){\r\n      return a % 2 < b % 2;\r\n    });\r\n    return A;\r\n  }\r\n};<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
    Problem Given an array\u00a0A\u00a0of non-negative integers, return an array consisting of all the even elements of\u00a0A, followed by all the odd elements of\u00a0A. You may…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[184],"tags":[222,409,408,23],"class_list":["post-3984","post","type-post","status-publish","format-standard","hentry","category-array","tag-easy","tag-even","tag-odd","tag-sort","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3984","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=3984"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3984\/revisions"}],"predecessor-version":[{"id":3986,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/3984\/revisions\/3986"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=3984"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=3984"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=3984"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}