What is the fastest way to solve Sort Array By Parity using two pointers?

Use a left pointer to track the next even placement and a right pointer to scan through the array. Swap when an even number is found and increment the left pointer.

Do I need to preserve the original order of numbers?

No, any arrangement where all even numbers appear before all odd numbers is acceptable unless a stable version is specifically requested.

What are common mistakes when using the two-pointer method?

Forgetting to increment the left pointer after a swap, swapping unnecessarily, and mismanaging the invariant tracking are typical errors.

Can this algorithm handle arrays of length 1?

Yes, a single-element array is already correctly partitioned by parity, so the algorithm simply returns it.

What is the time and space complexity of this approach?

It runs in O(n) time with O(1) extra space because each element is visited once and only a few pointers are maintained.

#905

Easy

auto_awesome双·指针·invariant

LeetCode 题解工作台

按奇偶排序数组

给你一个整数数组 nums ，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。返回满足此条件的任一数组作为答案。示例 1：输入： nums = [3,1,2,4] 输出： [2,4,3,1] 解释： [4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被…

数组双指针排序

题目描述

给你一个整数数组 nums，将 nums 中的的所有偶数元素移动到数组的前面，后跟所有奇数元素。

返回满足此条件的 任一数组 作为答案。

示例 1：

输入：nums = [3,1,2,4]
输出：[2,4,3,1]
解释：[4,2,3,1]、[2,4,1,3] 和 [4,2,1,3] 也会被视作正确答案。

示例 2：

输入：nums = [0]
输出：[0]

提示：

1 <= nums.length <= 5000
0 <= nums[i] <= 5000

lightbulb

解题思路

方法一：双指针

我们用两个指针 $i$ 和 $j$ 分别指向数组的首尾，当 $i < j$ 时，执行以下操作。

如果 $nums[i]$ 为偶数，则 $i$ 自增 $1$ 。
如果 $nums[j]$ 为奇数，则 $j$ 自减 $1$ 。
如果 $nums[i]$ 为奇数，且 $nums[j]$ 为偶数，则交换 $nums[i]$ 和 $nums[j]$ 。然后 $i$ 自增 $1$ ，而 $j$ 自减 $1$ 。

最后返回数组 $nums$ 即可。

时间复杂度 $O(n)$ ，其中 $n$ 是数组 $nums$ 的长度。空间复杂度 $O(1)$ 。

1

2

3

4

5

6

7

8

9

10

11

12

13

class Solution:
    def sortArrayByParity(self, nums: List[int]) -> List[int]:
        i, j = 0, len(nums) - 1
        while i < j:
            if nums[i] % 2 == 0:
                i += 1
            elif nums[j] % 2 == 1:
                j -= 1
            else:
                nums[i], nums[j] = nums[j], nums[i]
                i, j = i + 1, j - 1
        return nums

speed

复杂度分析

指标	值
时间	Depends on the final approach
空间	Depends on the final approach

psychology

面试官常问的追问

外企场景

question_mark
Look for candidate solutions using two pointers and minimal swaps.
question_mark
Ask about maintaining invariants to ensure no even numbers are lost in placement.
question_mark
Probe edge cases like arrays with all even or all odd numbers.

warning

常见陷阱

外企场景

error
Swapping incorrectly when both pointers point to even numbers, causing unnecessary operations.
error
Forgetting to increment the left pointer after a successful swap, breaking the invariant.
error
Assuming stability is required when any valid ordering suffices, leading to extra complexity.

swap_horiz

进阶变体

外企场景

arrow_right_alt
Sort array by parity while preserving original relative order of even and odd numbers (stable version).
arrow_right_alt
Move all multiples of k to the front while keeping the rest in any order, generalizing the parity pattern.
arrow_right_alt
Sort array into multiple partitions based on modulo classes instead of just even/odd separation.

help

常见问题

外企场景

继续练习

#922 按奇偶排序数组 II #923 三数之和的多种可能 #881 救生艇