画图/定义/伪代码/情况分析
不使用额外空间
nums=[1,2,3,4]
func f(nums) {
p1=0
p2=-1
if empty {
}
}
定义:[p1,p2]的是奇数 , (p2,end]的是偶数
情况讨论:
数组为空 return 数组
数组只有一个元素 return 数组
数组有偶数个 , 奇数个 , 好像没关系
[p1,p2]的后一个元素是奇数 , 直接p2++
后一个元素不是奇数 , 新增p3指针, 找到最近的一个奇数, swap(p2+1,p3) , 然后p2++ , 如果找不到p3, 直接return
p2没有后一个元素了,直接return
复杂度分析 :
全部元素都是奇数 , or 都是偶数 O(n) or 分布接近规律
我靠不好分析 , 主要是else里的for循环的情况:
使用额外空间 遍历一遍就行了 , 简单
开辟同样大小的数组 , 奇数放左边 , 偶数从右边开始放
//额外空间
func sortArrayByParity(A []int) []int {
len := len(A)
if len == 0 || len == 1 {
return A
}
new:=make([]int,len)
p1:=0
p2:=len-1
for i:=0;i<=len-1;i++ {
if A[i]%2==0 {
new[p1]=A[i]
p1++
} else {
new[p2]=A[i]
p2--
}
}
return new
}
//不使用额外空间
func sortArrayByParity1(A []int) []int {
len := len(A)
if len == 0 || len == 1 {
return A
}
//p1 := 0
p2 := -1
for p2+1 <= len-1 {
if A[p2+1]%2 == 0 {
p2++
} else {
p3:=p2+1
for i:=p3;i<=len-1;i++ {
if A[i]%2==0 {
tmp:=A[p3]
A[p3]=A[i]
A[i]=tmp
p2++
break
}
//优化 , 当p3往后遍历都没有奇数的时候 , 直接返回
if i==len-1 && A[i]%2==1 {
return A
}
}
}
}
return A
}
Sort Array By Parity
Sort Array By Parity
