LeetCode 2149 按符号重排数组元素（Rearrange Array Elements by Sign）：暴力、分组与双指针三解法全解析

LeetCode 2149 按符号重排数组元素（Rearrange Array Elements by Sign）：暴力、分组与双指针三解法全解析

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode

本文围绕 LeetCode 2149「按符号重排数组元素」展开，系统讲解暴力移位、分组归并、双指针三种解法在 Python / Java / C++ / JavaScript / C# / Go / Kotlin / Swift / Rust 中的完整实现，并给出每一解法的时间与空间复杂度分析以及常见陷阱。读者学完后，既能掌握这道典型数组重排题的多种解题路径，也能理解双指针在保持元素相对顺序前提下的高效应用，并可直接在本仓库的 Java 与 Kotlin 源码中找到可运行的参考实现。

题目背景与前置知识

问题描述

给定一个由n个整数组成的数组nums，其中n为偶数，且正整数的数量与负整数的数量恰好相等，数组中不包含0。要求重排该数组，使得：

• 每个正整数恰好出现在一个偶数下标（0, 2, 4, ...）；
• 每个负整数恰好出现在一个奇数下标（1, 3, 5, ...）；
• 正整数之间、负整数之间各自的相对顺序保持不变。

例如输入nums = [3, 1, -2, -5, 2, -4]，一个合法输出为[3, -2, 1, -5, 2, -4]。

前置知识

在动手实现之前，需要具备以下两块基础：

• 数组（Arrays）：理解数组的下标索引、遍历方式以及原地（in-place）修改的操作语义。本题的所有解法都建立在「按下标读写」这一基本操作之上。
• 双指针技巧（Two Pointers）：能够同时用多个指针跟踪数组中不同位置的写入进度。解法三正是利用i（偶数下标指针）与j（奇数下标指针）两个指针，在一次遍历中完成全部元素的落位。

解法一：暴力法（原地移位）

思路

逐位置处理数组：在遍历到下标i时，检查当前位置的元素符号是否已经满足要求——偶数下标应为正数、奇数下标应为负数。若已满足则跳过；若不满足，则向后寻找第一个符号正确的元素j，把该元素保存下来，将i到j-1之间的所有元素统一右移一位，再把保存的元素放到位置i。整个过程完全在原数组上完成，不需要额外的结果数组。

算法步骤

1. 遍历每个下标i：
   • 若下标为偶数且nums[i] > 0，或下标为奇数且nums[i] < 0，则当前位置已正确，继续下一个位置；
   • 否则，从i + 1开始向后寻找符号与nums[i]相反的第一个元素j；
   • 保存nums[j]，然后将i到j-1的元素依次右移一位；
   • 将保存的元素写入位置i。
2. 返回处理后的数组。

多语言实现

class Solution: def rearrangeArray(self, nums: List[int]) -> List[int]: n = len(nums) for i in range(n): if ((i % 2 == 0 and nums[i] > 0) or (i % 2 == 1 and nums[i] < 0)): continue j = i + 1 while j < n and ((nums[j] > 0) == (nums[i] > 0)): j += 1 tmp = nums[j] while j > i: nums[j] = nums[j - 1] j -= 1 nums[i] = tmp return nums

public class Solution { public int[] rearrangeArray(int[] nums) { int n = nums.length; for (int i = 0; i < n; i++) { if ((i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0)) { continue; } int j = i + 1; while (j < n && ((nums[j] > 0) == (nums[i] > 0))) { j++; } int temp = nums[j]; while (j > i) { nums[j] = nums[j - 1]; j--; } nums[i] = temp; } return nums; } }

class Solution { public: vector<int> rearrangeArray(vector<int>& nums) { int n = nums.size(); for (int i = 0; i < n; i++) { if ((i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0)) { continue; } int j = i + 1; while (j < n && ((nums[j] > 0) == (nums[i] > 0))) { j++; } int temp = nums[j]; while (j > i) { nums[j] = nums[j - 1]; j--; } nums[i] = temp; } return nums; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ rearrangeArray(nums) { let n = nums.length; for (let i = 0; i < n; i++) { if ((i % 2 === 0 && nums[i] > 0) || (i % 2 === 1 && nums[i] < 0)) { continue; } let j = i + 1; while (j < n && nums[j] > 0 === nums[i] > 0) { j++; } let temp = nums[j]; while (j > i) { nums[j] = nums[j - 1]; j--; } nums[i] = temp; } return nums; } }

public class Solution { public int[] RearrangeArray(int[] nums) { int n = nums.Length; for (int i = 0; i < n; i++) { if ((i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0)) { continue; } int j = i + 1; while (j < n && ((nums[j] > 0) == (nums[i] > 0))) { j++; } int tmp = nums[j]; while (j > i) { nums[j] = nums[j - 1]; j--; } nums[i] = tmp; } return nums; } }

func rearrangeArray(nums []int) []int { n := len(nums) for i := 0; i < n; i++ { if (i%2 == 0 && nums[i] > 0) || (i%2 == 1 && nums[i] < 0) { continue } j := i + 1 for j < n && ((nums[j] > 0) == (nums[i] > 0)) { j++ } tmp := nums[j] for j > i { nums[j] = nums[j-1] j-- } nums[i] = tmp } return nums }

class Solution { fun rearrangeArray(nums: IntArray): IntArray { val n = nums.size for (i in 0 until n) { if ((i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0)) { continue } var j = i + 1 while (j < n && (nums[j] > 0) == (nums[i] > 0)) { j++ } val tmp = nums[j] while (j > i) { nums[j] = nums[j - 1] j-- } nums[i] = tmp } return nums } }

class Solution { func rearrangeArray(_ nums: [Int]) -> [Int] { var nums = nums let n = nums.count for i in 0..<n { if (i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0) { continue } var j = i + 1 while j < n && (nums[j] > 0) == (nums[i] > 0) { j += 1 } let tmp = nums[j] while j > i { nums[j] = nums[j - 1] j -= 1 } nums[i] = tmp } return nums } }

impl Solution { pub fn rearrange_array(mut nums: Vec<i32>) -> Vec<i32> { let n = nums.len(); for i in 0..n { if (i % 2 == 0 && nums[i] > 0) || (i % 2 == 1 && nums[i] < 0) { continue; } let mut j = i + 1; while j < n && (nums[j] > 0) == (nums[i] > 0) { j += 1; } let tmp = nums[j]; while j > i { nums[j] = nums[j - 1]; j -= 1; } nums[i] = tmp; } nums } }

复杂度分析

• 时间复杂度：$O(n^2)$。最坏情况下，每个位置都可能触发一次长度为 $O(n)$ 的查找与整体右移。
• 空间复杂度：$O(1)$ 额外空间。所有操作均在原数组上进行。

该解法虽然正确，但平方级的时间开销使其仅适合作为理解问题结构的入门版本，实际应用中应优先采用下面的线性解法。

解法二：分组到两个数组

思路

题目要求正负交替出现，同时保持正数之间、负数之间各自的相对顺序。一个很自然的想法是：先把所有正数收集到一个列表、所有负数收集到另一个列表，然后再按下标规则交替写回原数组——正数写偶数下标，负数写奇数下标。由于两个列表内部天然保持了原数组中的相对顺序，写回后这一顺序也不会被破坏。

算法步骤

1. 创建两个列表：pos存放所有正数，neg存放所有负数。
2. 遍历输入数组，将每个数放入对应列表。
3. 按下标交错重建数组：
   • 将pos[i]写入下标2 * i；
   • 将neg[i]写入下标2 * i + 1。
4. 返回结果数组。

多语言实现

class Solution: def rearrangeArray(self, nums: List[int]) -> List[int]: pos, neg = [], [] for num in nums: if num > 0: pos.append(num) else: neg.append(num) i = 0 while 2 * i < len(nums): nums[2 * i] = pos[i] nums[2 * i + 1] = neg[i] i += 1 return nums

public class Solution { public int[] rearrangeArray(int[] nums) { List<Integer> pos = new ArrayList<>(); List<Integer> neg = new ArrayList<>(); for (int num : nums) { if (num > 0) { pos.add(num); } else { neg.add(num); } } int i = 0; while (2 * i < nums.length) { nums[2 * i] = pos.get(i); nums[2 * i + 1] = neg.get(i); i++; } return nums; } }

class Solution { public: vector<int> rearrangeArray(vector<int>& nums) { vector<int> pos, neg; for (int num : nums) { if (num > 0) { pos.push_back(num); } else { neg.push_back(num); } } int i = 0; while (2 * i < nums.size()) { nums[2 * i] = pos[i]; nums[2 * i + 1] = neg[i]; i++; } return nums; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ rearrangeArray(nums) { const pos = [], neg = []; for (const num of nums) { if (num > 0) { pos.push(num); } else { neg.push(num); } } let i = 0; while (2 * i < nums.length) { nums[2 * i] = pos[i]; nums[2 * i + 1] = neg[i]; i++; } return nums; } }

public class Solution { public int[] RearrangeArray(int[] nums) { List<int> pos = new List<int>(); List<int> neg = new List<int>(); foreach (int num in nums) { if (num > 0) pos.Add(num); else neg.Add(num); } int i = 0; while (2 * i < nums.Length) { nums[2 * i] = pos[i]; nums[2 * i + 1] = neg[i]; i++; } return nums; } }

func rearrangeArray(nums []int) []int { var pos, neg []int for _, num := range nums { if num > 0 { pos = append(pos, num) } else { neg = append(neg, num) } } i := 0 for 2*i < len(nums) { nums[2*i] = pos[i] nums[2*i+1] = neg[i] i++ } return nums }

class Solution { fun rearrangeArray(nums: IntArray): IntArray { val pos = mutableListOf<Int>() val neg = mutableListOf<Int>() for (num in nums) { if (num > 0) pos.add(num) else neg.add(num) } var i = 0 while (2 * i < nums.size) { nums[2 * i] = pos[i] nums[2 * i + 1] = neg[i] i++ } return nums } }

class Solution { func rearrangeArray(_ nums: [Int]) -> [Int] { var nums = nums var pos = [Int]() var neg = [Int]() for num in nums { if num > 0 { pos.append(num) } else { neg.append(num) } } var i = 0 while 2 * i < nums.count { nums[2 * i] = pos[i] nums[2 * i + 1] = neg[i] i += 1 } return nums } }

impl Solution { pub fn rearrange_array(mut nums: Vec<i32>) -> Vec<i32> { let mut pos = Vec::new(); let mut neg = Vec::new(); for &num in &nums { if num > 0 { pos.push(num); } else { neg.push(num); } } let mut i = 0; while 2 * i < nums.len() { nums[2 * i] = pos[i]; nums[2 * i + 1] = neg[i]; i += 1; } nums } }

复杂度分析

• 时间复杂度：$O(n)$。两次线性扫描（一次分组、一次交错写回）即可完成。
• 空间复杂度：$O(n)$。需要两个与正、负数数量等长的辅助列表。

该解法简单直观，是面试中最容易想到且不易出错的方案。它的唯一代价是额外的 $O(n)$ 空间，而解法三可以在同样 $O(n)$ 时间内把辅助空间压缩到仅结果数组本身。

解法三：双指针（单次遍历直接落位）

思路

既然输出数组的下标规律完全确定——正数固定落在偶数下标、负数固定落在奇数下标——我们就可以在一次遍历中完成所有元素的落位，而不必先分组再合并。维护两个写入指针：i指向下一个可用的偶数下标（用于写入正数），j指向下一个可用的奇数下标（用于写入负数）。扫描原数组时，遇到正数就写入res[i]并把i前进 2，遇到负数就写入res[j]并把j前进 2。由于扫描本身保留了原数组的顺序，两个指针各自推进也保证正数之间、负数之间的相对顺序不变。

算法步骤

1. 初始化i = 0（正数写入位置，偶数下标）与j = 1（负数写入位置，奇数下标）。
2. 创建一个与原数组等长的结果数组res。
3. 遍历输入数组中的每个数：
   • 若为正数，写入res[i]，然后i += 2；
   • 若为负数，写入res[j]，然后j += 2。
4. 返回res。

多语言实现

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

public class Solution { public int[] rearrangeArray(int[] nums) { int i = 0, j = 1; int[] res = new int[nums.length]; for (int k = 0; k < nums.length; k++) { if (nums[k] > 0) { res[i] = nums[k]; i += 2; } else { res[j] = nums[k]; j += 2; } } return res; } }

class Solution { public: vector<int> rearrangeArray(vector<int>& nums) { int i = 0, j = 1; vector<int> res(nums.size()); for (int k = 0; k < nums.size(); k++) { if (nums[k] > 0) { res[i] = nums[k]; i += 2; } else { res[j] = nums[k]; j += 2; } } return res; } };

class Solution { /** * @param {number[]} nums * @return {number[]} */ rearrangeArray(nums) { let i = 0, j = 1; const res = new Array(nums.length); for (let k = 0; k < nums.length; k++) { if (nums[k] > 0) { res[i] = nums[k]; i += 2; } else { res[j] = nums[k]; j += 2; } } return res; } }

public class Solution { public int[] RearrangeArray(int[] nums) { int i = 0, j = 1; int[] res = new int[nums.Length]; for (int k = 0; k < nums.Length; k++) { if (nums[k] > 0) { res[i] = nums[k]; i += 2; } else { res[j] = nums[k]; j += 2; } } return res; } }

func rearrangeArray(nums []int) []int { i, j := 0, 1 res := make([]int, len(nums)) for k := 0; k < len(nums); k++ { if nums[k] > 0 { res[i] = nums[k] i += 2 } else { res[j] = nums[k] j += 2 } } return res }

class Solution { fun rearrangeArray(nums: IntArray): IntArray { var i = 0 var j = 1 val res = IntArray(nums.size) for (k in nums.indices) { if (nums[k] > 0) { res[i] = nums[k] i += 2 } else { res[j] = nums[k] j += 2 } } return res } }

class Solution { func rearrangeArray(_ nums: [Int]) -> [Int] { var i = 0, j = 1 var res = Int for k in 0..<nums.count { if nums[k] > 0 { res[i] = nums[k] i += 2 } else { res[j] = nums[k] j += 2 } } return res } }

impl Solution { pub fn rearrange_array(nums: Vec<i32>) -> Vec<i32> { let mut i = 0usize; let mut j = 1usize; let mut res = vec![0i32; nums.len()]; for k in 0..nums.len() { if nums[k] > 0 { res[i] = nums[k]; i += 2; } else { res[j] = nums[k]; j += 2; } } res } }

复杂度分析

• 时间复杂度：$O(n)$。单次线性遍历，每个元素只被读写一次。
• 空间复杂度：$O(n)$。该空间来自结果数组本身；如果只统计额外辅助空间，则除了返回的结果数组外没有其他额外开销。

仓库源码印证

本仓库中收录的两种官方提交均采用这一双指针写法：

• java/2149-rearrange-array-elements-by-signs.java 中，Solution.rearrangeArray以i = 0, j = 1双指针初始化，遍历时按nums[k] > 0分别写入res[i]与res[j]，并将对应指针步进 2，最终返回结果数组；
• kotlin/2149-rearrange-array-elements-by-sign.kt 采用完全相同的双指针策略（局部变量命名为pos与neg），与本文给出的 Kotlin 实现一致。

从源码结构可以确认：双指针写法是该项目针对本题的推荐提交形态，其逻辑与本文解法三完全对应。

常见陷阱

混淆下标奇偶与符号的对应关系

最常见的错误是把「正数写偶数下标、负数写奇数下标」记反。一旦颠倒，结果数组中偶数位全是负数、奇数位全是正数，直接违反题目要求。记忆锚点：下标从 0 开始，0 是偶数，因此偶数位放正数，奇数位放负数。

未能保持相对顺序

题目明确要求正整数之间、负整数之间各自的相对顺序不得改变。若直接对原数组进行无策略的相邻交换或随意 swap，很可能破坏这一约束。解法二（分组列表）与解法三（双指针落位）都通过「顺序扫描 + 顺序写入」天然保证了相对顺序，是安全的选择。

忘记处理 0 或符号判断失误

虽然题目保证输入中不含 0，但实现时仍需注意：判断正负应使用num > 0与num < 0的显式比较，避免把 0 误归入某一侧（例如用num >= 0会把 0 当作正数），或依赖可能被 0 破坏的符号推断逻辑。确保符号判断与题目约束严格一致，代码在边界输入下才更稳健。

三种解法对比小结

实战建议：理解阶段可以从暴力法入手把握「偶数下标为正、奇数下标为负」的核心约束；面试作答首选解法三（双指针），它代码最简洁且只需要一次遍历；解法二则是思路最直白、最不易出错的备选方案。本文所有多语言实现均可在 articles/rearrange-array-elements-by-sign.md 及仓库对应语言的2149-*源码文件中对照查阅。

【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode