README.md

905. Sort Array By Parity (Easy)

Given an integer array nums, move all the even integers at the beginning of the array followed by all the odd integers.

Return any array that satisfies this condition.

 

Example 1:

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

Example 2:

Input: nums = [0]
Output: [0]

 

Constraints:

• 1 <= nums.length <= 5000
• 0 <= nums[i] <= 5000

Related Topics:
Array, Two Pointers, Sorting

Similar Questions:

• Sort Even and Odd Indices Independently (Easy)
• Largest Number After Digit Swaps by Parity (Easy)

Solution 1. STL

// OJ: https://leetcode.com/problems/sort-array-by-parity/
// Author: github.com/lzl124631x
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        sort(begin(A), end(A), [](int a, int b) { return a % 2 < b % 2; });
        return A;
    }
};

Solution 2. Two Pointers

// OJ: https://leetcode.com/problems/sort-array-by-parity/
// Author: github.com/lzl124631x
// Time: O(N)
// Space: O(1)
class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {
        for (int i = 0, j = A.size() - 1; i < j; ++i, --j) {
            while (i < j && A[i] % 2 == 0) ++i;
            while (i < j && A[j] % 2 != 0) --j;
            if (i < j) swap(A[i], A[j]);
        }
        return A;
    }
};