[数据结构与算法]leetcode-2149. 按符号重排数组(Java)

2149. 按符号重排数组

【题目描述】

给你一个下标从 0 开始的整数数组 nums ，数组长度为 偶数 ，由数目相等的正整数和负整数组成。

你需要 重排 nums 中的元素，使修改后的数组满足下述条件：

任意?连续 的两个整数 符号相反
对于符号相同的所有整数，保留 它们在 nums 中的 顺序 。
重排后数组以正整数开头。
重排元素满足上述条件后，返回修改后的数组。

示例 1：

输入：nums = [3,1,-2,-5,2,-4]
输出：[3,-2,1,-5,2,-4]
解释：
nums 中的正整数是 [3,1,2] ，负整数是 [-2,-5,-4] 。
重排的唯一可行方案是 [3,-2,1,-5,2,-4]，能满足所有条件。
像 [1,-2,2,-5,3,-4]、[3,1,2,-2,-5,-4]、[-2,3,-5,1,-4,2] 这样的其他方案是不正确的，因为不满足一个或者多个条件。?
示例 2：

输入：nums = [-1,1]
输出：[1,-1]
解释：
1 是 nums 中唯一一个正整数，-1 是 nums 中唯一一个负整数。
所以 nums 重排为 [1,-1] 。
?

提示：

2 <= nums.length <= 2 * 105
nums.length 是 偶数
1 <= |nums[i]| <= 105
nums 由 相等 数量的正整数和负整数组成

分析：本题需要满足三个要求，开头正整数、正负交替、并且保持原有顺序。

开头正正整数+正负交替 == 偶数项（正整数）奇数项（负整数）

至于保持原原有顺序，循环遍历，便是从头至尾，只需要判断正负，将其放置在奇偶项即可。

伪代码：

1. int len?= 长度，odd(奇数项)=1? even（偶数项）= 0; 返回数组 int[] ans = new int[len];?

?2. 循环遍历

每项的值?

如果大于0 放在偶数项，并且偶数项标志even += 2；

如果小于0 放在奇数项，并且奇数项标志odd+= 2；

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int len = nums.length;
        int odd = 1 ,even = 0;
        int[] ans = new int[len];
        for(int i = 0; i < len ; i++){
            int n = nums[i];
            if(n > 0 ) {
                ans[even] = n;
                even += 2;
            }else {
                ans[odd] = n;
                odd += 2;
            }
        } 
        return ans;
    }
}