Sort Array By Parity
tags: odd even modulo
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 <= A.length <= 5000
0 <= A[i] <= 5000
Implementation
|
|
The task is to sort an array in such a way that all the even integers come first followed by all the odd integers. There are many ways to achieve this, and any valid sorting is acceptable. Here’s one way to do it:
Approach:
- Initialize Pointers: Create two pointers
i
andj
. Seti
at the beginning of the array andj
at the end of the array. - Partition Elements: Loop until
i
is less thanj
.- If
nums[i]
is odd andnums[j]
is even, swap them. - If
nums[i]
is even, incrementi
. - If
nums[j]
is odd, decrementj
.
- If
- Return Result: The array will now have even elements at the beginning and odd elements at the end.
Code:
|
|
Example:
- Input:
nums = [3,1,2,4]
- Output:
[2,4,3,1]
(other valid outputs are also possible) - Explanation: Even numbers (2 and 4) are moved to the beginning, and odd numbers (3 and 1) are at the end.
Insights:
- Time Complexity: The time complexity is (O(n)), where (n) is the length of the array. The algorithm scans the array once.
- Space Complexity: The space complexity is (O(1)), as the sorting is done in place, and no additional space is used.
- In-Place Sorting: This solution sorts the original array in place, achieving a space-efficient solution.
|
|