按奇偶排序数组II（922）

题目

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

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

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

示例

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

提示

• 2 <= A.length <= 20000
• A.length % 2 == 0
• 0 <= A[i] <= 1000

算法

双指针

指针i从头部遍历数组，当指针i的奇偶性和A[i]不一致时，创建指向i+1的指针j，然后移动指针j去寻找和i奇偶性一致的A[j]，找到后调换A[i]和A[j]，然后继续移动指针i检查后面的数组元素

export const sortArrayByParityII = (A) => {
	for (let i = 0; i < A.length; i++) {
		if (A[i] % 2 === i % 2) {
			continue;
		} else {
			let j = i + 1;
			while (A[j] % 2 !== i % 2 && j < A.length) {
				j++;
			}
			[A[i], A[j]] = [A[j], A[i]];
		}
	}
	return A;
};

两次遍历

遍历两次数组，第一次找到所有偶数并依次写入结果数组res的偶数位0, 2, 4, 6...；第二次找到所有奇数并依次写入结果数组res的奇数位1, 3, 5, 7...

export const sortArrayByParityII = (A) => {
	const res = [];
	let oddIndex = 1,
		evenIndex = 0;
	A.forEach((item) => {
		if (item % 2 === 0) {
			res[evenIndex] = item;
			evenIndex += 2;
		}
	});
	A.forEach((item) => {
		if (item % 2 === 1) {
			res[oddIndex] = item;
			oddIndex += 2;
		}
	});
	return res;
};