905. Sort Array By Parity

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.

Input: nums = [0]
Output: [0]

题目分析： 题目要求我们按奇偶排序数组，所有的偶数应该在所有的奇数之前。这是一个很常见的数组操作问题，可以通过双指针的方法来解决。

解题思路：

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;
};