脚撕LeetCode(922)Easy
题目地址：https://leetcode-cn.com/problems/sort-array-by-parity-ii/
给定一个非负整数数组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
https://leetcode-cn.com/problems/sort-array-by-parity-ii/
这道题题意很简单，就是给你一个数组，把它弄成偶数下标的数字是偶数，奇数下标的数字是奇数
一、不难想到的爆破法
新建一个数组，然后遍历原数组将奇数放在奇数位，偶数放在偶数位
执行结果如下：
61 / 61 个通过测试用例
状态：通过
执行用时: 3 ms
内存消耗: 41.9 MB
public static int[] sortArrayByParityIIMe(int[] nums) {
int doubleIndex = 0;
int singleIndex = 1;
int len = nums.length;
int[] ans = new int[len];
for (int num : nums) {
if (num % 2 == 0) {
ans[doubleIndex] = num;
doubleIndex += 2;
} else {
ans[singleIndex] = num;
singleIndex += 2;
}
}
return ans;
}爆破法的时间有83%，但是空间只有10%，说明还是得在原来的数组上操作。
一开始我最早的想法确实是在原数组上操作，后来发现超时了，当我把爆破法1提交上去之后才想到，超时可能只是我某个循环条件写的不好，而不是对循环此时真的有控制。于是我写了第二个爆破法，接近双百
二、爆破法2
定义双指针，一个遍历双数下标一个遍历单数下标，然后如果碰到不符合条件的就交换
执行结果如下：
61 / 61 个通过测试用例
状态：通过
执行用时: 2 ms
内存消耗: 38.9 MB
public static int[] sortArrayByParityIIMe2(int[] nums) {
int doubleIndex = 0;
int singleIndex = 1;
int len = nums.length;
int temp;
while (singleIndex < len && doubleIndex < len) {
while (doubleIndex < len && (nums[doubleIndex] & 1) == 0) doubleIndex += 2;
while (singleIndex < len && (nums[singleIndex] & 1) == 1) singleIndex += 2;
if (doubleIndex >= len || singleIndex >= len) break;
temp = nums[doubleIndex];
nums[doubleIndex] = nums[singleIndex];
nums[singleIndex] = temp;
}
return nums;
}我就说这道题应该很简单，遇到超时不要急着变换思路；得出来的教训：可能是循环出了问题。
本文参与 腾讯云自媒体同步曝光计划，分享自微信公众号。
原始发表：2021-06-08，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
腾讯云开发者
