Description
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
Solutions
Solution 1: Two Pointers
We use two pointers $i$ and $j$ to point to the beginning and end of the array respectively. When $i < j$, we perform the following operations.
- If $nums[i]$ is even, then increment $i$ by $1$.
- If $nums[j]$ is odd, then decrement $j$ by $1$.
- If $nums[i]$ is odd and $nums[j]$ is even, then swap $nums[i]$ and $nums[j]$. Then increment $i$ by $1$, and decrement $j$ by $1$.
Finally, return the array $nums$.
The time complexity is $O(n)$, where $n$ is the length of the array $nums$. The space complexity is $O(1)$.
1
2
3
4
5
6
7
8
9
10
11
12 | class Solution:
def sortArrayByParity(self, nums: List[int]) -> List[int]:
i, j = 0, len(nums) - 1
while i < j:
if nums[i] % 2 == 0:
i += 1
elif nums[j] % 2 == 1:
j -= 1
else:
nums[i], nums[j] = nums[j], nums[i]
i, j = i + 1, j - 1
return nums
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19 | class Solution {
public int[] sortArrayByParity(int[] nums) {
int i = 0, j = nums.length - 1;
while (i < j) {
if (nums[i] % 2 == 0) {
++i;
} else if (nums[j] % 2 == 1) {
--j;
} else {
int t = nums[i];
nums[i] = nums[j];
nums[j] = t;
++i;
--j;
}
}
return nums;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16 | class Solution {
public:
vector<int> sortArrayByParity(vector<int>& nums) {
int i = 0, j = nums.size() - 1;
while (i < j) {
if (nums[i] % 2 == 0) {
++i;
} else if (nums[j] % 2 == 1) {
--j;
} else {
swap(nums[i++], nums[j--]);
}
}
return nums;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12 | func sortArrayByParity(nums []int) []int {
for i, j := 0, len(nums)-1; i < j; {
if nums[i]%2 == 0 {
i++
} else if nums[j]%2 == 1 {
j--
} else {
nums[i], nums[j] = nums[j], nums[i]
}
}
return nums
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14 | function sortArrayByParity(nums: number[]): number[] {
for (let i = 0, j = nums.length - 1; i < j; ) {
if (nums[i] % 2 === 0) {
++i;
} else if (nums[j] % 2 === 1) {
--j;
} else {
[nums[i], nums[j]] = [nums[j], nums[i]];
++i;
--j;
}
}
return nums;
}
|