https://leetcode.com/articles/sort-array-by-parity/
Example 1:
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
If we want to do the sort in-place, we can use quicksort, a standard textbook algorithm.
Algorithm
We'll maintain two pointers
i
and j
. The loop invariant is everything below i
has parity 0
(ie. A[k] % 2 == 0
when k < i
), and everything above j
has parity 1
.
Then, there are 4 cases for
(A[i] % 2, A[j] % 2)
:- If it is
(0, 1)
, then everything is correct:i++
andj--
. - If it is
(1, 0)
, we swap them so they are correct, then continue. - If it is
(0, 0)
, only thei
place is correct, so wei++
and continue. - If it is
(1, 1)
, only thej
place is correct, so wej--
and continue.
Throughout all 4 cases, the loop invariant is maintained, and
j-i
is getting smaller. So eventually we will be done with the array sorted as desired.- Time Complexity: , where is the length of
A
. Each step of the while loop makesj-i
decrease by at least one. (Note that while quicksort is normally, this is because we only need one pass to sort the elements.) - Space Complexity: in additional space complexity.
public int[] sortArrayByParity(int[] A) {
int i = 0, j = A.length - 1;
while (i < j) {
if (A[i] % 2 > A[j] % 2) {
int tmp = A[i];
A[i] = A[j];
A[j] = tmp;
}
if (A[i] % 2 == 0)
i++;
if (A[j] % 2 == 1)
j--;
}
return A;
}
public int[] sortArrayByParity(int[] A) {
int[] ans = new int[A.length];
int t = 0;
for (int i = 0; i < A.length; ++i)
if (A[i] % 2 == 0)
ans[t++] = A[i];
for (int i = 0; i < A.length; ++i)
if (A[i] % 2 == 1)
ans[t++] = A[i];
return ans;
}
public int[] sortArrayByParity(int[] A) {
Integer[] B = new Integer[A.length];
for (int t = 0; t < A.length; ++t)
B[t] = A[t];
Arrays.sort(B, (a, b) -> Integer.compare(a % 2, b % 2));
for (int t = 0; t < A.length; ++t)
A[t] = B[t];
return A;
/*
* Alternative:
*
* return Arrays.stream(A)
*
* .boxed()
*
* .sorted((a, b) -> Integer.compare(a%2, b%2))
*
* .mapToInt(i -> i)
*
* .toArray();
*
*/
}