Leetcode 922. Sort Array By Parity II

文章作者：Tyan
博客：noahsnail.com  |  CSDN  |  简书

1. Description

2. Solution

解析：Version 1，每次碰到一个位置与数值不对应的数时，都找一个与它奇偶性相反、位置与数值不对应的数交换。Version 2两个指针分别查找位置与数值不对应的奇数和偶数，然后交换数值。

• Version 1

class Solution:
    def sortArrayByParityII(self, nums: List[int]) -> List[int]:
        for i in range(len(nums)):
            if i % 2 != nums[i] % 2:
                j = i + 1
                while j % 2 == nums[j] % 2:
                    j += 2
                nums[i], nums[j] = nums[j], nums[i]
                
        return nums

• Version 2

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

Reference

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