[LeetCode] 2149. Rearrange Array Elements by Sign

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:
Every consecutive pair of integers have opposite signs.
For all integers with the same sign, the order in which they were present in nums is preserved.
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.

按符号重排数组。

给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。 你需要 重排 nums 中的元素，使修改后的数组满足下述条件： 1. 任意 连续 的两个整数 符号相反 2. 对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。 3. 重排后数组以正整数开头。 重排元素满足上述条件后，返回修改后的数组。

思路

思路是双指针。这里我们需要两个指针 a 和 b 分别去找 input 数组里出现的正数和负数，然后按照规则放入结果里。因为最后要求输出的数组要求正负数交替出现且先出现正数，所以代码里就可以直接先找正数，再找负数。

复杂度

时间O(n)
空间O(n)

代码

Java实现

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int p = 0;
        int a = 0;
        int b = 0;
		int[] res = new int[nums.length];
        while (p < nums.length) {
            while (nums[a] < 0) {
                a++;
            }
            res[p++] = nums[a++];
            while (nums[b] > 0) {
                b++;
            }
            res[p++] = nums[b++];
        }
        return res;
    }
}