905. Sort Array By Parity

Problem

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

https://leetcode.cn/problems/sort-array-by-parity/

Example 1:

Input: nums = [3,1,2,4]
Output: [2,4,3,1]
Explanation: The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Example 2:

Input: nums = [0]
Output: [0]

Constraints:

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

Test Cases

1 2	class Solution: def sortArrayByParity(self, nums: List[int]) -> List[int]:

solution_test.py

import pytest

from solution import Solution


def verify(res, nums):
    assert sorted(res) == sorted(nums)
    is_even = True
    for num in res:
        if is_even:
            if num & 1:
                is_even = False
        else:
            assert num & 1 == 1


@pytest.mark.parametrize('nums, expected', [
    ([3,1,2,4], [2,4,3,1]),
    ([0], [0]),
])
@pytest.mark.parametrize('sol', [Solution()])
def test_solution(sol, nums, expected):
    res = sol.sortArrayByParity(nums.copy())
    if res != expected:
        verify(res, nums)

Thoughts

用两个指针分别从数组首尾向中间扫描，即 i = 0 和 j = n - 1。如果 nums[i] 是偶数则右移 i 直到遇到奇数（或与 j 相遇），如果 nums[j] 是奇数则左移 j 直到遇到偶数（或与 i 相遇）。停下时如果 i 和 j 未相遇，说明 nums[i] 是奇数而 nums[j] 是偶数，将二者交换。重复处理直到 i 和 j 相遇即可。

时间复杂度 O(n)，空间复杂度 O(1)。

Code

solution.py

class Solution:
    def sortArrayByParity(self, nums: list[int]) -> list[int]:
        i = 0
        j = len(nums) - 1
        while i < j:
            while i < j and nums[i] & 1 == 0:
                i += 1
            while i < j and nums[j] & 1 == 1:
                j -= 1
            if i < j:
                nums[i], nums[j] = nums[j], nums[i]

        return nums

反向引用
- 922. Sort Array By Parity II

本文除了题目描述（Problem）部分之外，其他内容由 Calf 原创，采用 CC BY-NC-SA 4.0 许可协议，转载请注明出处。