Leetcode Python超琐碎笔记: 905-Sort Array By Parity

问题地址，难度：Easy

若有错误之处请予以指正:)

问题描述

Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.

Example 1:

Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.

Note:
1 <= A.length <= 5000
0 <= A[i] <= 5000

题意分析

把偶数奇数分成前后两部分输出，空间上in-place当然最好。

我的实现及调优过程

方法1：92 ms

暴力没什么好说的。

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        even = []
        odd = []
        for n in A:
            if n % 2 == 0:
                even.append(n)
            else:
                odd.append(n)
        return even + odd

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法2：92 ms

使用列表生成式代替for循环，并无卵用，估计测试集太小了。

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        return [x for x in A if x % 2 == 0] + [x for x in A if x % 2 > 0]
        

• 时间复杂度：O(n)
• 空间复杂度：O(n)

方法3：96 ms

In-place 方法，速度相当。直接在A上做手脚。取两个指针分别指头尾，取余后两个余数有四种情况，分别处理：

• 前>后
• 前<后
• 前=后=0
• 前=后=1

class Solution:
    def sortArrayByParity(self, A):
        """
        :type A: List[int]
        :rtype: List[int]
        """
        i, j = 0, len(A) - 1
        while i < j:
            i_re = A[i] % 2
            j_re = A[j] % 2
            # odd - even
            if i_re > j_re:
                A[i], A[j] = A[j], A[i]
                i += 1
                j -= 1
            # even - odd
            elif i_re < j_re: 
                i += 1
                j -= 1
            else:
                if i_re == 0:
                    i += 1
                else:
                    j -= 1
        return A

• 时间复杂度：O(n)
• 空间复杂度：O(1)

方法3-Golang版：72 ms

刚好这两天在看Golang的基本语法，拿来耍下。快了一丢丢（居然还是个100%），然而我是完全不能理解那些Python下60多ms是怎么刷出来的啊啊啊，卒。

func sortArrayByParity(A []int) []int {
    i := 0
    j := len(A) - 1
    var i_re, j_re int
    for ; i<j ;{
        i_re = A[i] % 2
        j_re = A[j] % 2
        if i_re > j_re {
            c := A[i] //这里一开始还出了你懂的bug，我已经被Python惯坏
            A[i] = A[j]
            A[j] = c
            i += 1
            j -= 1
        } else if i_re < j_re { 
            i += 1
            j -= 1
        } else {
            if i_re == 0 { i += 1} else {
                j -= 1}
        }
    }
    return A
}

• 时间复杂度：O(n)
• 空间复杂度：O(1)