双指针:
数组从两头向中间靠近。左边的为奇数指针,右边的为偶数指针。左边指针在没有遇到偶数时,就向右移动,遇到偶数立即停止;右边指针在没有遇到奇数时,向左边移动,遇到奇数时,进行奇偶指针元素交换。交换之后切换到奇数指针工作。这个方法只遍历一遍数组。
#
# 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可
#
#
# @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是逻辑运算。&是位运算)