代码随想录——按奇偶排序数组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] 也会被接受

思路

方法一：两次遍历

创建一个新数组：

• 遍历一遍数组把所有的偶数放进，ans[0]，ans[2]，ans[4]，以此类推
• 遍历一遍数组把所有的奇数放进，ans[1]，ans[3]，ans[5]，以此类推

java代码如下：

class Solution {
	public int[] sortArrarByParity(int[] nums){
		int n = nums.length;
		int[] ans = new int[n];

		int i = 0;//从下标0开始装数，先装满偶数位
		for(int x : nums){
			if(x % 2 == 0){//如果是偶数
				ans[i] = x;
				i += 2;
			}
		}
		i = 1;//从下标1开始，继续装满奇数位
		for(int x : nums){
			if(x % 2 == 1){
				ans[i] = x;
				i += 2; 
			}
		}
		return ans; 
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

方法二：双指针法

简单来说：就是不断遍历，如果在偶数位遇到了奇数，那么就找在奇数位上找一个偶数，进行替换

具体步骤：分别维护两个指针i 和 j，分别指向数组的偶数下标（i）和奇数下标（j），之后每一步遍历的时候，如果偶数位nums[i]是奇数（偶数位上的奇数），则不断向前移动j（每次移动两步），直到遇到下一个偶数（此时的偶数为奇数位的上偶数），然后直接将nums[i]和nums[j]交换，最终下来，能够将所有的整数放在正确的位置上。

注意的是，不管是i还是j，每次移动都是两位，因为分别指向偶数位和奇数位

以[4，2，5，7]为例，开始遍历：
nums[0] = 4，为偶数，继续；
nums[2] = 5，为奇数，返现了一个偶数位的奇数，开始找奇数位的偶数，进行替换，nums[1] = 2，满足条件，交换，数组变为[4，5，2，7]；

java代码如下：

class Solution {
	public int[] sortArrayByParityII(int[] nums){
		int n = nums.length;
		int j = 1;//j指向奇数位
		for(int i = 0;  i < n; i += 2){//i指向偶数位，开始遍历
			if(nums[i] % 2 == 1){//如果偶数位nums[i]遇到了一个奇数
				while(nums[j] % 2 == 1){//就在奇数位找一个偶数，循环条件为nums[j] % 2 == 1，即只要nunms[j]是奇数就一直循环下去，知道找到一个奇数位的偶数
					j += 2;
				}
				swap(nums, i ,j);//此时退出while循环的j才是满足nums[j] % 2 == 0  的j
			}		
		}
		return nums;
	}
	
	public void swap(int[] nums, int i ,int j){
		int temp = nums[i];
		nums[i] = nums[j];
		nums[j] = temp;
	}  
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21