Sort Array By Parity

画图/定义/伪代码/情况分析

不使用额外空间
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
}

本作品采用《CC 协议》，转载必须注明作者和本文链接