Leetcode 905 Sort Array By Parity

发表于 |

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.
You may return any answer array that satisfies this condition.

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. 1 <= A.length <= 5000
  2. 0 <= A[i] <= 5000

分析：

  1. 要将数组中所有偶数排在奇数前面，并且还不限制顺序，并且长度还不超过5000，已经是特别简单了
  2. 如果使用O(n)的空间，我们可以将偶数全部取出来存一个数组，将奇数全部取出来存一个数组，最后将两个数组合并即可。
  3. 如果使用O(1)的空间，我们就只能做swap，用两个指针，一个指着奇数，一个指着偶数然后交换即可。
1
2
3
4
5
6
7
8
9
10
11
12
# O(1) space
class Solution(object):
    def sortArrayByParity(self, A):
        i,j = 0,0
        # 使用i记录奇数的位置，然后j往后遍历，找到偶数后进行交换
        while i < len(A):
            if j < i: j = i
            while j < len(A) and A[i] % 2 != 0 and A[j] % 2 != 0: j += 1
            if j >= len(A): break
            A[i], A[j] = A[j], A[i]
            i += 1
        return A