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.lengthis even.- Half of the integers in
numsare even. 0 <= nums[i] <= 1000
Follow Up: Could you solve it in-place?
Test Cases
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
评论需要 JavaScript。