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 <= 50000 <= 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).
PythonJavaC++GoTypeScriptRustJavaScript
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(code-box)
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;
}
}(code-box)
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;
}
};(code-box)
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
}(code-box)
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;
}(code-box)
impl Solution {
pub fn sort_array_by_parity(mut nums: Vec<i32>) -> Vec<i32> {
let (mut i, mut j) = (0, nums.len() - 1);
while i < j {
if nums[i] % 2 == 0 {
i += 1;
} else if nums[j] % 2 == 1 {
j -= 1;
} else {
nums.swap(i, j);
i += 1;
j -= 1;
}
}
nums
}
}(code-box)
/**
* @param {number[]} nums
* @return {number[]}
*/
var sortArrayByParity = function (nums) {
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;
};(code-box)
