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

simoncos · · 331 次点击 · · 开始浏览

### 问题描述

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`

### 我的实现及调优过程

##### 方法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

``````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

``````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)

0 回复

• 请尽量让自己的回复能够对别人有帮助
• 支持 Markdown 格式, **粗体**、~~删除线~~、``单行代码``
• 支持 @ 本站用户；支持表情（输入 : 提示），见 Emoji cheat sheet
• 图片支持拖拽、截图粘贴等方式上传

### 问题描述

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`

### 我的实现及调优过程

##### 方法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

``````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

``````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)