# 905. Sort Array By Parity

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

1. 设置两个指针，`left``right`，其中`left`从数组的开始处向后移动，`right`从数组的末尾向前移动。
2. `left`指向偶数，`left++`，向右移动；当`right`指向奇数，`right--`，向左移动。
3. 如果`left`指向奇数且`right`指向偶数，则交换这两个元素。
4. 重复上述过程，直到`left >= right`

### 时间和空间复杂度分析：

**时间复杂度：**这个算法的时间复杂度是O(n)，其中n是数组的长度。这是因为我们使用两个指针从数组的两端向中间扫描，每个元素最多被访问一次。

**空间复杂度：**这个算法的空间复杂度是O(1)，因为我们只是在原数组上进行交换操作，没有使用额外的数组或数据结构。

### 为什么双指针方法在此问题上有效：

Problem Analysis: The task is to sort an array by parity, with all even elements preceding all odd ones. This is a common array manipulation issue that can be addressed using the two-pointers technique.

Solution Idea:

1. Set two pointers, `left` and `right`, where `left` moves forward from the start of the array and `right` moves backward from the end of the array.
2. Move `left` forward when it points to an even number; move `right` backward when it points to an odd number.
3. If `left` points to an odd number and `right` points to an even number, swap these two elements.
4. Repeat the above steps until `left >= right`.

### Time and Space Complexity Analysis:

Time Complexity: The time complexity of this algorithm is O(n), where n is the length of the array. This is because we use two pointers to scan from both ends of the array towards the center, with each element being visited at most once.

Space Complexity: The space complexity of this algorithm is O(1), as we are merely swapping elements within the original array without using any additional arrays or data structures.

### Why the Two-Pointer Approach is Effective for this Problem:

The two-pointer approach is effective for this problem because it leverages the specific nature of the task: separating even and odd numbers. By setting one pointer to scan forward from the beginning for odd numbers and another to scan backward from the end for even numbers, we can efficiently separate the evens and odds within the array in a single pass.

This method is efficient because it operates directly on the original array, reducing extra memory allocation and movement while ensuring that each element is only examined and moved once. Therefore, it is a fast and memory-efficient method for partitioning an array.

TypeScript代码：

``````function sortArrayByParity(nums: number[]): number[] {
let l = 0, r = nums.length - 1;
while (l < r) {
while (l < r && nums[l] % 2 === 0) l++;
while (l < r && nums[r] % 2 !== 0) r--;
if (l < r) {
[nums[l], nums[r]] = [nums[r], nums[l]];
l++;
r--;
}
}
return nums;
};``````

This site uses Akismet to reduce spam. Learn how your comment data is processed.