LeetCode 905 Sort Array By Parity 全解：从排序到双指针的四类实现与源码印证

LeetCode 905 Sort Array By Parity 全解从排序到双指针的四类实现与源码印证【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode本文基于仓库 articles/sort-array-by-parity.md 展开系统讲解 LeetCode 905「按奇偶排序数组」的四种主流解法基于比较的排序、双数组收集、相向双指针与同向快慢指针并结合仓库内 Java/Kotlin 的实际提交代码印证其工程实现。读完你将掌握奇偶校验num 1与num % 2的差异、原地分区partition与双指针的经典写法并能针对不同语言约束选择最优实现。前置知识在动手解题前建议先掌握以下基础数组Arrays数组的遍历与原地in-place修改双指针技巧Two Pointers用于实现最优的 $O(n)$ 原地分区方案位运算基础Bit Manipulation使用按位与num 1或取模num % 2判断奇偶性。这些前置知识在仓库同类题目中反复出现例如 articles/move-zeroes.md、articles/remove-element.md、articles/sort-colors.md 均以数组遍历与双指针分区为核心。一、解法一直接排序Sorting直觉Intuition我们想要所有偶数排在奇数前面。把奇偶性even/odd当作排序键就可以直接复用语言内置的排序偶数奇偶性为 0奇数为 1按奇偶性排序自然把偶数排在最前。这种思路只要求满足「偶数在前、奇数在后」不要求组内有序因此比较器只需比较奇偶性无需比较数值大小。算法步骤Algorithm使用基于num 1或num % 2的自定义比较器对数组排序比较结果为0偶数的元素排在结果为1奇数的元素之前返回排序后的数组。各语言实现class Solution: def sortArrayByParity(self, nums: List[int]) - List[int]: nums.sort(key lambda x: x 1) return numspublic class Solution { public int[] sortArrayByParity(int[] nums) { Integer[] A Arrays.stream(nums).boxed().toArray(Integer[]::new); Arrays.sort(A, (a, b) - (a 1) - (b 1)); return Arrays.stream(A).mapToInt(Integer::intValue).toArray(); } }class Solution { public: vectorint sortArrayByParity(vectorint nums) { sort(nums.begin(), nums.end(), { return (a 1) (b 1); }); return nums; } };class Solution { /** * param {number[]} nums * return {number[]} */ sortArrayByParity(nums) { return nums.sort((a, b) (a 1) - (b 1)); } }public class Solution { public int[] SortArrayByParity(int[] nums) { Array.Sort(nums, (a, b) (a 1).CompareTo(b 1)); return nums; } }func sortArrayByParity(nums []int) []int { sort.Slice(nums, func(i, j int) bool { return (nums[i] 1) (nums[j] 1) }) return nums }class Solution { fun sortArrayByParity(nums: IntArray): IntArray { return nums.sortedBy { it and 1 }.toIntArray() } }class Solution { func sortArrayByParity(_ nums: [Int]) - [Int] { return nums.sorted { ($0 1) ($1 1) } } }impl Solution { pub fn sort_array_by_parity(mut nums: Veci32) - Veci32 { nums.sort_by_key(|x| x 1); nums } }复杂度分析时间复杂度$O(n \log n)$空间复杂度$O(1)$ 或 $O(n)$取决于具体排序算法的实现如原地快排为 $O(\log n)$ 栈空间归并等则需 $O(n)$ 辅助空间。二、解法二双数组收集Array / Two Lists直觉Intuition与其排序不如单趟扫描把元素分成两组偶数收集到一个列表奇数收集到另一个列表再拼接。这样完全避开了基于比较的排序开销。算法步骤Algorithm创建两个列表一个放偶数一个放奇数遍历数组根据奇偶性把每个元素放入对应列表将偶数列表拼接在奇数列表之前将结果复制回原数组或直接返回拼接结果。各语言实现class Solution: def sortArrayByParity(self, nums: List[int]) - List[int]: even, odd [], [] for num in nums: if num 1: odd.append(num) else: even.append(num) idx 0 for e in even: nums[idx] e idx 1 for o in odd: nums[idx] o idx 1 return numspublic class Solution { public int[] sortArrayByParity(int[] nums) { ListInteger even new ArrayList(); ListInteger odd new ArrayList(); for (int num : nums) { if ((num 1) 1) { odd.add(num); } else { even.add(num); } } int idx 0; for (int e : even) { nums[idx] e; } for (int o : odd) { nums[idx] o; } return nums; } }class Solution { public: vectorint sortArrayByParity(vectorint nums) { vectorint even, odd; for (int num : nums) { if (num 1) { odd.push_back(num); } else { even.push_back(num); } } int idx 0; for (int e : even) { nums[idx] e; } for (int o : odd) { nums[idx] o; } return nums; } };class Solution { /** * param {number[]} nums * return {number[]} */ sortArrayByParity(nums) { const even []; const odd []; for (let num of nums) { if (num % 2) { odd.push(num); } else { even.push(num); } } let idx 0; for (let e of even) { nums[idx] e; } for (let o of odd) { nums[idx] o; } return nums; } }public class Solution { public int[] SortArrayByParity(int[] nums) { Listint even new Listint(); Listint odd new Listint(); foreach (int num in nums) { if ((num 1) 1) { odd.Add(num); } else { even.Add(num); } } int idx 0; foreach (int e in even) { nums[idx] e; } foreach (int o in odd) { nums[idx] o; } return nums; } }func sortArrayByParity(nums []int) []int { even : []int{} odd : []int{} for _, num : range nums { if num 1 1 { odd append(odd, num) } else { even append(even, num) } } idx : 0 for _, e : range even { nums[idx] e idx } for _, o : range odd { nums[idx] o idx } return nums }class Solution { fun sortArrayByParity(nums: IntArray): IntArray { val even mutableListOfInt() val odd mutableListOfInt() for (num in nums) { if (num and 1 1) { odd.add(num) } else { even.add(num) } } var idx 0 for (e in even) { nums[idx] e } for (o in odd) { nums[idx] o } return nums } }class Solution { func sortArrayByParity(_ nums: [Int]) - [Int] { var even [Int]() var odd [Int]() for num in nums { if num 1 1 { odd.append(num) } else { even.append(num) } } var result [Int]() result.append(contentsOf: even) result.append(contentsOf: odd) return result } }impl Solution { pub fn sort_array_by_parity(mut nums: Veci32) - Veci32 { let mut even Vec::new(); let mut odd Vec::new(); for num in nums { if num 1 1 { odd.push(num); } else { even.push(num); } } let mut idx 0; for e in even { nums[idx] e; idx 1; } for o in odd { nums[idx] o; idx 1; } nums } }复杂度分析时间复杂度$O(n)$空间复杂度$O(n)$需要两个额外列表。仓库源码印证另一种「双指针 新数组」变体仓库中的 java/0905-sort-array-by-parity.java 给出了一种紧凑的变体不建两个列表而是新建一个等长数组用i从头和j从尾两个索引同时填充——遇到偶数放到前端、奇数放到后端class Solution { public int[] sortArrayByParity(int[] nums) { int[] arr new int[nums.length]; int i 0; int j nums.length-1; for(int n : nums){ if(n%2 0){ arr[i] n; i; } else{ arr[j] n; j--; } } return arr; } }这段代码同样达到 $O(n)$ 时间、$O(n)$ 空间但只用一个辅助数组逻辑更简洁偶数从前端顺序写入奇数从后端倒序写入天然满足「偶数在前、奇数在后」且无需拼接步骤。可见「双列表收集」与「单辅助数组双端填充」本质同源都是空间换时间的线性解法。三、解法三相向双指针Two Pointers - I直觉Intuition可以用两个指针在数组两端原地分区左指针负责找出需要移到右边的奇数右指针标记奇数应该去的位置。当左指针发现奇数时把它与右指针所指元素交换从而把奇数推到数组末尾。算法步骤Algorithm初始化两个指针i指向开头j指向末尾当i j时循环若nums[i]是奇数与nums[j]交换并让j减一否则i加一该元素是偶数已就位返回修改后的数组。各语言实现class Solution: def sortArrayByParity(self, nums: List[int]) - List[int]: i, j 0, len(nums) - 1 while i j: if nums[i] 1: nums[i], nums[j] nums[j], nums[i] j - 1 else: i 1 return numspublic class Solution { public int[] sortArrayByParity(int[] nums) { int i 0, j nums.length - 1; while (i j) { if ((nums[i] 1) 1) { int temp nums[i]; nums[i] nums[j]; nums[j--] temp; } else { i; } } return nums; } }class Solution { public: vectorint sortArrayByParity(vectorint nums) { int i 0, j nums.size() - 1; while (i j) { if ((nums[i] 1) 1) { swap(nums[i], nums[j]); j--; } else { i; } } return nums; } };class Solution { /** * param {number[]} nums * return {number[]} */ sortArrayByParity(nums) { let i 0, j nums.length - 1; while (i j) { if ((nums[i] 1) 1) { [nums[i], nums[j]] [nums[j], nums[i]]; j--; } else { i; } } return nums; } }public class Solution { public int[] SortArrayByParity(int[] nums) { int i 0, j nums.Length - 1; while (i j) { if ((nums[i] 1) 1) { int temp nums[i]; nums[i] nums[j]; nums[j] temp; j--; } else { i; } } return nums; } }func sortArrayByParity(nums []int) []int { i, j : 0, len(nums) - 1 for i j { if nums[i] 1 1 { nums[i], nums[j] nums[j], nums[i] j-- } else { i } } return nums }class Solution { fun sortArrayByParity(nums: IntArray): IntArray { var i 0 var j nums.size - 1 while (i j) { if (nums[i] and 1 1) { nums[i] nums[j].also { nums[j] nums[i] } j-- } else { i } } return nums } }class Solution { func sortArrayByParity(_ nums: [Int]) - [Int] { var nums nums var i 0, j nums.count - 1 while i j { if nums[i] 1 1 { nums.swapAt(i, j) j - 1 } else { i 1 } } return nums } }impl Solution { pub fn sort_array_by_parity(mut nums: Veci32) - Veci32 { let (mut i, mut j) (0, nums.len() as i32 - 1); while i j { if nums[i as usize] 1 1 { nums.swap(i as usize, j as usize); j - 1; } else { i 1; } } nums } }复杂度分析时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间纯原地交换。仓库源码印证仓库中的 kotlin/0905-sort-array-by-parity.kt 正是这一相向双指针思路的直接实现左指针i遇到奇数时与右边界odd交换并回退右边界遇到偶数则前进直到两指针相遇class Solution { fun sortArrayByParity(nums: IntArray): IntArray { var odd nums.lastIndex var i 0 while (i odd) { if (nums[i] % 2 1) { val temp nums[i] nums[i] nums[odd] nums[odd] temp odd-- } else { i } } return nums } }注意这里用的是nums[i] % 2 1而非 1在本题目数据范围内非负整数两种写法等价其通用性与负数场景的差异将在下文「常见陷阱」中详细说明。四、解法四同向快慢指针Two Pointers - II直觉Intuition该方案使用同向移动的慢指针与快指针。慢指针l记录下一个偶数应该放置的位置快指针r负责扫描整个数组。每当发现偶数就把它交换到位置l并让l前进一位从而把所有偶数收集到数组前端。这与 articles/move-zeroes.md 中把零移到末尾的思路是同构的——只是把目标元素从「零」换成了「偶数」。算法步骤Algorithm初始化慢指针l为0用快指针r遍历数组若nums[r]是偶数交换nums[l]与nums[r]并令l加一返回修改后的数组。各语言实现class Solution: def sortArrayByParity(self, nums: List[int]) - List[int]: l 0 for r in range(len(nums)): if nums[r] % 2 0: nums[l], nums[r] nums[r], nums[l] l 1 return numspublic class Solution { public int[] sortArrayByParity(int[] nums) { for (int l 0, r 0; r nums.length; r) { if (nums[r] % 2 0) { int temp nums[l]; nums[l] nums[r]; nums[r] temp; l; } } return nums; } }class Solution { public: vectorint sortArrayByParity(vectorint nums) { for (int l 0, r 0; r nums.size(); r) { if (nums[r] % 2 0) { swap(nums[l], nums[r]); l; } } return nums; } };class Solution { /** * param {number[]} nums * return {number[]} */ sortArrayByParity(nums) { for (let l 0, r 0; r nums.length; r) { if (nums[r] % 2 0) { [nums[l], nums[r]] [nums[r], nums[l]]; l; } } return nums; } }public class Solution { public int[] SortArrayByParity(int[] nums) { int l 0; for (int r 0; r nums.Length; r) { if (nums[r] % 2 0) { int temp nums[l]; nums[l] nums[r]; nums[r] temp; l; } } return nums; } }func sortArrayByParity(nums []int) []int { l : 0 for r : 0; r len(nums); r { if nums[r] % 2 0 { nums[l], nums[r] nums[r], nums[l] l } } return nums }class Solution { fun sortArrayByParity(nums: IntArray): IntArray { var l 0 for (r in nums.indices) { if (nums[r] % 2 0) { nums[l] nums[r].also { nums[r] nums[l] } l } } return nums } }class Solution { func sortArrayByParity(_ nums: [Int]) - [Int] { var nums nums var l 0 for r in 0..nums.count { if nums[r] % 2 0 { nums.swapAt(l, r) l 1 } } return nums } }impl Solution { pub fn sort_array_by_parity(mut nums: Veci32) - Veci32 { let mut l 0; for r in 0..nums.len() { if nums[r] % 2 0 { nums.swap(l, r); l 1; } } nums } }复杂度分析时间复杂度$O(n)$空间复杂度$O(1)$ 额外空间。四种方案的取舍对照方案时间空间是否原地稳定性适用场景直接排序$O(n\log n)$$O(1)$/ $O(n)$视语言而定否代码最简洁适合快速实现双数组收集$O(n)$$O(n)$否是允许额外空间逻辑直白相向双指针$O(n)$$O(1)$是否追求原地与最小空间同向快慢指针$O(n)$$O(1)$是是保持相对顺序面试高频考察「同向快慢指针」是四者中唯一同时满足线性时间、常数空间与稳定性的方案它只把偶数向前交换奇数之间的相对顺序不会被打乱因此也适合要求稳定的变种题。五、常见陷阱Common Pitfalls陷阱一与右边界交换后误递增左指针在「相向双指针」方案中把奇数交换到右端后绝不能顺手让左指针i也加一。因为从右侧换过来的元素尚未被检查它可能依然是奇数需要下一轮继续与更靠前的右边界交换。只有确认当前左指针元素为偶数无需移动时才递增i。若在交换后同时执行i与j--可能漏处理换过来的奇数导致分区不完整。陷阱二对负数使用取模判断奇偶虽然本题数据范围只含非负整数但在某些语言中num % 2对负数会产生反直觉的结果——负奇数的余数会是-1而非1例如-3 % 2 -1导致num % 2 1判断失败。使用按位与num 1判断奇偶更安全也更高效任何奇数的最低二进制位都是 1与 1 做与运算恒为 1与正负无关。这也是仓库 articles/sort-array-by-parity.md 中 Python、Go、Swift 等多语言实现优先采用 1的原因。陷阱三语言细节差异Java 中int[]是原始类型数组无法直接传 lambda 给Arrays.sort需要先装箱为Integer[]排序后再拆箱见解法一 Java 实现Kotlin 的sortedBy返回新列表需toIntArray()转回IntArray若想原地修改可改用IntArray下标交换见仓库 Kotlin 实现Swift 中sorted是非原地版本原地交换需使用swapAt见解法三 Swift 实现。六、延伸阅读与总结本题是「按条件分区」类题目的经典模板掌握后可以顺带攻克仓库中的一系列同构问题articles/move-zeroes.md把 0 移到末尾与本题互为镜像articles/remove-element.md原地移除指定值同样是快慢指针分区articles/sort-colors.md三色分区把相向双指针扩展为三分区articles/valid-palindrome-ii.md双指针在字符串上的应用。完整源码可在仓库对应语言目录查看Java 版见 java/0905-sort-array-by-parity.javaKotlin 版见 kotlin/0905-sort-array-by-parity.kt其余语言解法与本题指南 articles/sort-array-by-parity.md 一一对应。一句话总结面试中优先给出「同向快慢指针」——它同时满足 $O(n)$ 时间、$O(1)$ 空间与稳定性若允许额外空间「双数组收集」最易写对而判断奇偶一律用num 1避免负数取模的坑。【免费下载链接】leetcodeLeetcode solutions项目地址: https://gitcode.com/GitHub_Trending/leetcode1/leetcode创作声明：本文部分内容由AI辅助生成（AIGC），仅供参考