GoCalf Calf 的自留地 · 昙花一现

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

python
class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
solution_test.py下载完整源码
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

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

评论需要 JavaScript。