922. Sort Array By Parity II

Problem

Given an array of integers nums, half of the integers in nums are odd, and the other half are even.

Sort the array so that whenever nums[i] is odd, i is odd, and whenever nums[i] is even, i is even.

Return any answer array that satisfies this condition.

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

Example 1:

Input: nums = [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Example 2:

Input: nums = [2,3]
Output: [2,3]

Constraints:

2 <= nums.length <= 2 * 10⁴
nums.length is even.
Half of the integers in nums are even.
0 <= nums[i] <= 1000

Follow Up: Could you solve it in-place?

Test Cases

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

solution_test.py

import pytest

from solution import Solution


def verify(res, nums):
    assert sorted(res) == sorted(nums)
    assert all([i % 2 == 0 for i in res[::2]])
    assert all([i % 2 != 0 for i in res[1::2]])


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

Thoughts

905. Sort Array By Parity 的进阶版。

用同样的逻辑处理，只是指针 i 指向偶数下标，j 指向奇数下标。

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

Code

solution.py

class Solution:
    def sortArrayByParityII(self, nums: list[int]) -> list[int]:
        n = len(nums)
        i, j = 0, 1
        while i < n and j < n:
            while i < n and nums[i] % 2 == 0:
                i += 2
            while j < n and nums[j] % 2 != 0:
                j += 2
            if i < n and j < n:
                nums[i], nums[j] = nums[j], nums[i]

        return nums

本文引用
- 905. Sort Array By Parity

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