LeetCode: 2149-Rearrange Array Elements by Sign 解題紀錄

Last Updated on 2022-01-23 by Clay

題目

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:

1. Every consecutive pair of integers have opposite signs.
2. For all integers with the same sign, the order in which they were present in nums is preserved.
3. The rearranged array begins with a positive integer.

Return the modified array after rearranging the elements to satisfy the aforementioned conditions.

Example 1:

Input: nums = [3,1,-2,-5,2,-4]
Output: [3,-2,1,-5,2,-4]
Explanation:
The positive integers in nums are [3,1,2]. The negative integers are [-2,-5,-4].
The only possible way to rearrange them such that they satisfy all conditions is [3,-2,1,-5,2,-4].
Other 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.  

Example 2:

Input: nums = [-1,1]
Output: [1,-1]
Explanation:
1 is the only positive integer and -1 the only negative integer in nums.
So nums is rearranged to [1,-1].

Constraints:

• 2 <= nums.length <= 2 * 105
• nums.length is even
• 1 <= |nums[i]| <= 105
• nums consists of equal number of positive and negative integers.

題目給定一個保證正負數數量相等的陣列，嘗試按照正負數出現的順序，重新排列成正-負-正-負…… 這樣的陣列並回傳。

---

解題思路

我自己使用的方法是開一個新的陣列，並在陣列長度跟原始陣列相等前，每次都開始在原始陣列中搜尋下一個正數或負數，並將正數和負數最後找到的位置保存起來，在下一次開始尋找時從那個位置重新開始尋找。

複雜度

Time Complexity	O(2*n)
Space Complexity	O(n)

C++ 範例程式碼

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        vector<int> ans;
        int pi = 0;
        int ni = 0;
        int times = nums.size() / 2;

        for (int t=0; t<times; ++t) {
            for (int i=pi; i<nums.size(); ++i) {
                if (nums[i] > 0) {
                    ans.push_back(nums[i]);
                    pi = i+1;
                    break;
                }
            }
            
            for (int i=ni; i<nums.size(); ++i) {
                if (nums[i] < 0) {
                    ans.push_back(nums[i]);
                    ni = i+1;
                    break;
                }
            }
        }
        
        return ans;
    }
};

Python 範例程式碼

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        ans = []
        pi = 0
        ni = 0
        
        for _ in range(len(nums)//2):
            for i in range(pi, len(nums)):
                if nums[i] > 0:
                    ans.append(nums[i])
                    pi = i + 1
                    break
            
            for i in range(ni, len(nums)):
                if nums[i] < 0:
                    ans.append(nums[i])
                    ni = i + 1
                    break
        
        return ans
        

---

References

• https://leetcode.com/problems/rearrange-array-elements-by-sign/

---

Read More

• LeetCode 解題紀錄目錄