题解 | #调整数组顺序使奇数位于偶数前面(二)#

双指针：

数组从两头向中间靠近。左边的为奇数指针，右边的为偶数指针。左边指针在没有遇到偶数时，就向右移动，遇到偶数立即停止；右边指针在没有遇到奇数时，向左边移动，遇到奇数时，进行奇偶指针元素交换。交换之后切换到奇数指针工作。这个方法只遍历一遍数组。

#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
# 
# @param array int整型一维数组 
# @return int整型一维数组
#
class Solution:
    def reOrderArrayTwo(self , array: List[int]) -> List[int]:
        i=0
        j=len(array)-1
        while i<j:#当左右指针没有相遇时
            while (i<len(array)) and (array[i]%2==1):#左边指针碰到偶数，停下来；没有碰到继续走
                i=i+1
            while (j>=0) and (array[j]%2==0):#右边指针碰到奇数，停下来；没有碰到继续走
                j=j-1
            if i<j:
                array[i],array[j]=array[j],array[i]
        return array    

时间复杂度：O(n)，其中n为数组的长度，双指针最多只遍历数组一次

空间复杂度：O(1)，常数级变量，无额外辅助空间

tips:（1）最后面的if语句需要是因为，在最后一步，左指针在第一个偶数停下来，右指针会有最后一个奇数停下来，这个时候，不要发生交换。所以才添加交换前判断的语句。

（2） while (i<len(array))和while (j>=0)的添加，是因为当出现数组全为奇数或者全为偶数的特殊情况时，要有一个终止的条件。

当i变成数组原长度大小时，i<len(array)会短路，(array[i]%2==1)此语句不会运行，就不会出现数组越界的情况。里面的逻辑与用"and"，而不是"&"。（and是逻辑运算。&是位运算）