What is the key approach for solving the 'Rearrange Array Elements by Sign' problem?

The problem can be efficiently solved using a two-pointer technique where one pointer tracks positive integers and the other tracks negative integers. These pointers can then be used to rearrange the elements in the correct alternating order.

How do I handle edge cases like arrays with only two elements?

For small arrays, such as those with just two elements, the solution should simply swap the elements if necessary, as they are already small enough to handle directly.

What is the time complexity of the solution?

The time complexity is O(n), where n is the length of the array, as the array is traversed once during the rearrangement process.

How does GhostInterview help with the 'Rearrange Array Elements by Sign' problem?

GhostInterview guides you through the solution by reinforcing two-pointer scanning techniques and helping you practice the logic necessary to maintain the alternating pattern efficiently.

Can I optimize the space complexity of this problem?

Yes, the space complexity can be optimized to O(1) by performing in-place swaps to rearrange the elements instead of using additional space for tracking the positions of positive and negative integers.

#2149

Medium

auto_awesome双·指针·invariant

LeetCode 题解工作台

按符号重排数组

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

数组双指针模拟

题目描述

给你一个下标从 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 * 10⁵
nums.length 是偶数
1 <= |nums[i]| <= 10⁵
nums 由相等数量的正整数和负整数组成

不需要原地进行修改。

lightbulb

解题思路

方法一：双指针

我们先创建一个长度为 $n$ 的数组 $\textit{ans}$ ，然后使用两个指针 $i$ 和 $j$ 分别指向 $\textit{ans}$ 的偶数下标和奇数下标，初始时 $i = 0$ , $j = 1$ 。

遍历数组 $\textit{nums}$ ，如果当前元素 $x$ 为正整数，则将 $x$ 放入 $\textit{ans}[i]$ ，并将 $i$ 增加 $2$ ；否则将 $x$ 放入 $\textit{ans}[j]$ ，并将 $j$ 增加 $2$ 。

最后返回 $\textit{ans}$ 即可。

时间复杂度 $O(n)$ ，空间复杂度 $O(n)$ 。其中 $n$ 为数组 $\textit{nums}$ 的长度。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def rearrangeArray(self, nums: List[int]) -> List[int]:
        ans = [0] * len(nums)
        i, j = 0, 1
        for x in nums:
            if x > 0:
                ans[i] = x
                i += 2
            else:
                ans[j] = x
                j += 2
        return ans

speed

复杂度分析

指标	值
时间	O(n)
空间	O(n)

psychology

面试官常问的追问

外企场景

question_mark
Does the candidate demonstrate an understanding of two-pointer techniques for separating positive and negative integers?
question_mark
Can the candidate describe how they would handle large input sizes efficiently?
question_mark
Does the candidate focus on maintaining the alternating pattern while ensuring minimal computational overhead?

warning

常见陷阱

外企场景

error
Mixing up the order of positive and negative integers when swapping or rearranging them.
error
Failing to consider edge cases, such as arrays with only two elements.
error
Not maintaining the required alternating sign pattern after rearrangement.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Handling arrays with additional constraints, such as arrays of larger sizes.
arrow_right_alt
Modifying the solution to handle other conditions, such as multiple positive-negative swaps.
arrow_right_alt
Optimizing for space complexity, using in-place swapping or tracking positions more efficiently.

help

常见问题

外企场景

继续练习

#2161 根据给定数字划分数组 #2109 向字符串添加空格 #2105 给植物浇水 II