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。整个过程完全在原数组上完成不需要额外的结果数组。算法步骤遍历每个下标i若下标为偶数且nums[i] 0或下标为奇数且nums[i] 0则当前位置已正确继续下一个位置否则从i 1开始向后寻找符号与nums[i]相反的第一个元素j保存nums[j]然后将i到j-1的元素依次右移一位将保存的元素写入位置i。返回处理后的数组。多语言实现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 numspublic 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: vectorint rearrangeArray(vectorint 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: Veci32) - Veci32 { 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)$ 额外空间。所有操作均在原数组上进行。该解法虽然正确但平方级的时间开销使其仅适合作为理解问题结构的入门版本实际应用中应优先采用下面的线性解法。解法二分组到两个数组思路题目要求正负交替出现同时保持正数之间、负数之间各自的相对顺序。一个很自然的想法是先把所有正数收集到一个列表、所有负数收集到另一个列表然后再按下标规则交替写回原数组——正数写偶数下标负数写奇数下标。由于两个列表内部天然保持了原数组中的相对顺序写回后这一顺序也不会被破坏。算法步骤创建两个列表pos存放所有正数neg存放所有负数。遍历输入数组将每个数放入对应列表。按下标交错重建数组将pos[i]写入下标2 * i将neg[i]写入下标2 * i 1。返回结果数组。多语言实现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 numspublic class Solution { public int[] rearrangeArray(int[] nums) { ListInteger pos new ArrayList(); ListInteger 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: vectorint rearrangeArray(vectorint nums) { vectorint 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) { Listint pos new Listint(); Listint neg new Listint(); 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*i1] neg[i] i } return nums }class Solution { fun rearrangeArray(nums: IntArray): IntArray { val pos mutableListOfInt() val neg mutableListOfInt() 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: Veci32) - Veci32 { 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。由于扫描本身保留了原数组的顺序两个指针各自推进也保证正数之间、负数之间的相对顺序不变。算法步骤初始化i 0正数写入位置偶数下标与j 1负数写入位置奇数下标。创建一个与原数组等长的结果数组res。遍历输入数组中的每个数若为正数写入res[i]然后i 2若为负数写入res[j]然后j 2。返回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 respublic 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: vectorint rearrangeArray(vectorint nums) { int i 0, j 1; vectorint 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: Veci32) - Veci32 { 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 破坏的符号推断逻辑。确保符号判断与题目约束严格一致代码在边界输入下才更稳健。三种解法对比小结解法核心思想时间复杂度额外空间相对顺序暴力法原地查找正确符号元素并整体右移$O(n^2)$$O(1)$保持分组到两个数组正负数分别收集后交错写回$O(n)$$O(n)$保持双指针正负指针各自步进 2 单次落位$O(n)$$O(n)$结果数组保持实战建议理解阶段可以从暴力法入手把握「偶数下标为正、奇数下标为负」的核心约束面试作答首选解法三双指针它代码最简洁且只需要一次遍历解法二则是思路最直白、最不易出错的备选方案。本文所有多语言实现均可在 articles/rearrange-array-elements-by-sign.md 及仓库对应语言的2149-*源码文件中对照查阅。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考