{"id":9470,"date":"2022-02-04T17:01:40","date_gmt":"2022-02-05T01:01:40","guid":{"rendered":"https:\/\/zxi.mytechroad.com\/blog\/?p=9470"},"modified":"2022-02-04T17:06:04","modified_gmt":"2022-02-05T01:06:04","slug":"leetcode-2149-rearrange-array-elements-by-sign","status":"publish","type":"post","link":"https:\/\/zxi.mytechroad.com\/blog\/two-pointers\/leetcode-2149-rearrange-array-elements-by-sign\/","title":{"rendered":"\u82b1\u82b1\u9171 LeetCode 2149. Rearrange Array Elements by Sign"},"content":{"rendered":"\n

You are given a 0-indexed<\/strong> integer array nums<\/code> of even<\/strong> length consisting of an equal<\/strong> number of positive and negative integers.<\/p>\n\n\n\n

You should rearrange<\/strong> the elements of nums<\/code> such that the modified array follows the given conditions:<\/p>\n\n\n\n

  1. Every consecutive pair<\/strong> of integers have opposite signs<\/strong>.<\/li>
  2. For all integers with the same sign, the order<\/strong> in which they were present in nums<\/code> is preserved<\/strong>.<\/li>
  3. The rearranged array begins with a positive integer.<\/li><\/ol>\n\n\n\n

    Return the modified array after rearranging the elements to satisfy the aforementioned conditions<\/em>.<\/p>\n\n\n\n

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

    Input:<\/strong> nums = [3,1,-2,-5,2,-4]\nOutput:<\/strong> [3,-2,1,-5,2,-4]\nExplanation:<\/strong>\nThe positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].\nThe only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].\nOther ways such as [1,-2,2,-5,3,-4], [3,1,2,-2,-5,-4], [-2,3,-5,1,-4,2] are incorrect because they do not satisfy one or more conditions.  \n<\/pre>\n\n\n\n
    Example 2:<\/strong><\/p>\n\n\n\n
    Input:<\/strong> nums = [-1,1]\nOutput:<\/strong> [1,-1]\nExplanation:<\/strong>\n1 is the only positive integer and -1 the only negative integer in nums.\nSo nums is rearranged to [1,-1].\n<\/pre>\n\n\n\n
    Constraints:<\/strong><\/p>\n\n\n\n
    • 2 <= nums.length <= 2 * 105<\/sup><\/code><\/li>
    • nums.length<\/code> is even<\/strong><\/li>
    • 1 <= |nums[i]| <= 105<\/sup><\/code><\/li>
    • nums<\/code> consists of equal<\/strong> number of positive and negative integers.<\/li><\/ul>\n\n\n\n
      Solution 1: Split and merge<\/strong><\/h2>\n\n\n\n
      Create two arrays to store positive and negative numbers.<\/p>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(n)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector rearrangeArray(vector& nums) {\n    vector pos;\n    vector neg;\n    for (int x : nums)\n      (x > 0 ? pos : neg).push_back(x);\n    vector ans;\n    for (int i = 0; i < pos.size(); ++i) {\n      ans.push_back(pos[i]);\n      ans.push_back(neg[i]);\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n\n\n\n
      Solution 2: Two Pointers<\/strong><\/h2>\n\n\n\n
      Use two pointers to store the next pos \/ neg.<\/p>\n\n\n\n
      Time complexity: O(n)
      Space complexity: O(n)<\/p>\n\n\n\n
      \n
      C++<\/h2>\n
      \n\n
      \n\/\/ Author: Huahua\nclass Solution {\npublic:\n  vector rearrangeArray(vector& nums) {\n    vector ans(nums.size());    \n    int pos = 0;\n    int neg = 1;\n    for (int x : nums) {\n      int& index = x > 0 ? pos : neg;\n      ans[index] = x;\n      index += 2;\n    }\n    return ans;\n  }\n};\n<\/pre>\n<\/div><\/div>\n","protected":false},"excerpt":{"rendered":"
      You are given a 0-indexed integer array nums of even length consisting of an equal number of positive and negative integers. You should rearrange the elements of nums such that the modified array follows the given conditions:…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[176],"tags":[20,177,762,175],"class_list":["post-9470","post","type-post","status-publish","format-standard","hentry","category-two-pointers","tag-array","tag-medium","tag-rearrange","tag-two-pointers","entry","simple"],"_links":{"self":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9470","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=9470"}],"version-history":[{"count":2,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9470\/revisions"}],"predecessor-version":[{"id":9473,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/posts\/9470\/revisions\/9473"}],"wp:attachment":[{"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/media?parent=9470"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/categories?post=9470"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/zxi.mytechroad.com\/blog\/wp-json\/wp\/v2\/tags?post=9470"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}