Medium

题目描述

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

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

  1. 任意 连续 的两个整数符号 相反
  2. 对于符号相同的所有整数，保留 它们在 nums 中的 顺序
  3. 重排后的数组以 正整数 开头

请你返回满足上述条件的重排数组。

示例 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 * 10^5
  • nums.length 是 偶数
  • 1 <= |nums[i]| <= 10^5
  • nums 由相等数量的正整数和负整数组成

进阶： 可以不使用额外空间并在原数组上操作吗？

解题思路

这道题要求我们重新排列数组，使得正负数交替出现，且保持相同符号数字的相对顺序。

解法一：双指针直接填充（推荐）

最直观的思路是利用题目给出的规律：最终数组的偶数位置（0,2,4…）应该放正数，奇数位置（1,3,5…）应该放负数。

我们可以遍历原数组，用两个指针分别指向结果数组中应该放正数和负数的位置：

  • pos = 0：指向下一个应该放正数的位置（偶数索引）
  • neg = 1：指向下一个应该放负数的位置（奇数索引）

遇到正数就放到 pos 位置并让 pos += 2，遇到负数就放到 neg 位置并让 neg += 2。

这种方法时间复杂度为 O(n)，空间复杂度为 O(1)（不包括结果数组）。

解法二：分离再合并

先将正数和负数分别提取出来，然后交替合并。这种方法需要额外的空间来存储正数和负数数组，空间复杂度稍高。

第一种解法更优，因为它直接在结果数组上操作，避免了额外的存储开销。

代码实现

class Solution {
public:
    vector<int> rearrangeArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> result(n);
        int pos = 0, neg = 1;  // pos指向偶数位置，neg指向奇数位置
        
        for (int num : nums) {
            if (num > 0) {
                result[pos] = num;
                pos += 2;
            } else {
                result[neg] = num;
                neg += 2;
            }
        }
        
        return result;
    }
};

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        n = len(nums)
        result = [0] * n
        pos, neg = 0, 1  # pos指向偶数位置，neg指向奇数位置
        
        for num in nums:
            if num > 0:
                result[pos] = num
                pos += 2
            else:
                result[neg] = num
                neg += 2
        
        return result

public class Solution {
    public int[] RearrangeArray(int[] nums) {
        int n = nums.Length;
        int[] result = new int[n];
        int pos = 0, neg = 1;  // pos指向偶数位置，neg指向奇数位置
        
        foreach (int num in nums) {
            if (num > 0) {
                result[pos] = num;
                pos += 2;
            } else {
                result[neg] = num;
                neg += 2;
            }
        }
        
        return result;
    }
}

/**
 * @param {number[]} nums
 * @return {number[]}
 */
var rearrangeArray = function(nums) {
    const n = nums.length;
    const result = new Array(n);
    let pos = 0, neg = 1;  // pos指向偶数位置，neg指向奇数位置
    
    for (const num of nums) {
        if (num > 0) {
            result[pos] = num;
            pos += 2;
        } else {
            result[neg] = num;
            neg += 2;
        }
    }
    
    return result;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度类型值说明
时间复杂度O(n)只需要遍历一次原数组
空间复杂度O(1)除了结果数组外，只使用了常数个额外变量

相关题目