LeetCode 922.按奇偶排序数组2

给定一个非负整数数组 nums， nums 中一半整数是 奇数 ，一半整数是 偶数 。

对数组进行排序，以便当 nums[i] 为奇数时，i 也是 奇数 ；当 nums[i] 为偶数时， i 也是 偶数 。

你可以返回 任何满足上述条件的数组作为答案 。

示例 1：

输入：nums = [4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
示例 2：

输入：nums = [2,3]
输出：[2,3]

提示：

2 <= nums.length <= 2 * 10${}^4$
nums.length 是偶数
nums 中一半是偶数
0 <= nums[i] <= 1000

进阶：可以不使用额外空间解决问题吗？

同向双指针，左指针l左边[0, l)是已经排好序的部分，如果右指针指向的值和左指针l的奇偶性相同，就交换左右指针指向的值，然后递增左指针l；否则右移右指针，直到找到和l奇偶性相同的值：

class Solution {
public:vector<int> sortArrayByParityII(vector<int>& nums) {int l = 0;int r = 0;int n = nums.size();while (r < n) {if ((nums[r] & 1) != (l & 1)) {++r;} else {swap(nums[l], nums[r]);++l;// 此处修改r的代码可以去掉，因为l最多比r多1// 这发生在l和r指向同一个值的位置，且该值与l的奇偶性相同时// 这一情况下，l会移动到下一位置，l的奇偶性就会改变// 即l与r指向的值的奇偶性就会不同，然后下次循环就会右移r// 效果与此处的赋值相同r = max(l, r);}}return nums;}
};

如果nums的长度为n，则此算法时间复杂度为O(n)，空间复杂度为O(1)。