21-调整数组顺序使奇数位于偶数前面

题目

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

思路

双指针。一个指向头，一个指向尾。遍历的时候，交换，使得前面为奇数，后面为偶数。时间复杂度O(n)。

代码

class Solution:
    def exchange(self, nums: List[int]) -> List[int]:
        ptr = 0
        tail = len(nums) - 1
        while ptr < tail:
            # 向前移动，至到指向偶数
            while nums[ptr] & 1 == 1 and ptr < tail:
                ptr += 1
            # 向后移动，至到指向奇数
            while nums[tail] & 1 != 1 and ptr < tail:
                tail -= 1
            # 交换当前指针的两个数
            if tail > ptr:
                nums[ptr], nums[tail] = nums[tail], nums[ptr]
        return nums