按符号重排数组

标签: 数组 双指针 模拟

难度: 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 * 105
  • nums.length 是 偶数
  • 1 <= |nums[i]| <= 105
  • nums 由 相等 数量的正整数和负整数组成

不需要原地进行修改。

Submission

运行时间: 87 ms

内存: 39.6 MB

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        l1,l2 = [],[]
        for c in nums:
            if c > 0:
                l1.append(c)
            else:
                l2.append(c)
        nums[::2],nums[1::2] = l1,l2
        return nums

Explain

此题解首先通过遍历给定的数组 `nums`，将所有正整数和负整数分别存储在两个列表 `l1` 和 `l2` 中。遍历一次完成后，已经成功地将正负数分开，并且保持了它们在原数组中的顺序。接下来，利用 Python 列表的切片操作，将 `nums` 数组的偶数位置填充为 `l1` 中的元素，奇数位置填充为 `l2` 中的元素。这样操作的结果是，数组中的正负数交替出现，且以正数开头，符合题目要求。最后返回修改后的 `nums` 数组。

时间复杂度: O(n)

空间复杂度: O(n)

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        l1, l2 = [], []  # 初始化两个列表分别存储正数和负数
        for c in nums:  # 遍历数组，根据正负分别放入 l1 或 l2
            if c > 0:
                l1.append(c)
            else:
                l2.append(c)
        nums[::2], nums[1::2] = l1, l2  # 使用切片操作交替填充 nums，偶数索引填充正数，奇数索引填充负数
        return nums  # 返回重排后的数组

Explore

选择以正数开头而不是负数开头进行数组重排通常是基于题目的具体要求。如果题目没有特别指定起始符号，通常会默认以正数开头，因为这可能是更常见的场景或更符合题目出题者的预期。在实际应用中，这种选择可能也更符合常规的数据处理习惯。

是的，即使输入的数组已经是正负交替且以正数开头，当前的算法实现仍然会执行分离正负数和重新填充数组的步骤，这会导致不必要的计算和内存使用。优化方法可以包括首先检查数组是否已满足条件，如果是，则直接返回原数组，从而减少不必要的操作。

使用两个列表来分别存储正数和负数确实会增加内存使用，特别是在处理大数据量时。此外，这种方法还涉及多次遍历数据：一次用于分离正负数，另一次用于重组数组。这可能会导致较高的时间复杂度和空间复杂度，尤其是在数据量大时。可以考虑使用原地算法（in-place algorithm）来减少空间复杂度，例如通过双指针技术直接在原数组上操作，避免使用额外的存储空间。

题解通过确保偶数索引位置填充正数，奇数索引位置填充负数的方式来保证重排后的数组满足正负交替出现的条件。由于数组从零开始编号，通过这种方式可以确信偶数索引的正数后面紧跟的是奇数索引的负数，反之亦然。这种方法有效地利用了数组的索引特性，保证了每对相邻的整数符号相反。