LeetCode.905-按奇偶排序数组(Sort Array By Parity)
01 看题和准备
今天介绍的是LeetCode算法题中Easy级别的第212题（顺位题号是905）。给定一个非负整数数组A，返回一个由A的所有偶数元素组成的数组，后跟A的所有奇数元素。 你可以返回满足此条件的任何答案数组。例如：
输入：[3,1,2,4] 输出：[2,4,3,1] 说明：[4,2,3,1]，[2,4,1,3]和[4,2,1,3]也是正确答案。
注意：
-
1 <= A.length <= 5000 0 <= A[i] <= 5000
02 第一种解法
将数组A中的偶数元素存到List中，奇数元素存到List2中，创建一个新的数组result，长度和A相等，先遍历List，将偶数元素存入result的前面，再遍历List2，将奇数元素跟在偶数元素后面。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public int[] sortArrayByParity(int[] A) {
List<Integer> list = new ArrayList<Integer>();
List<Integer> list2 = new ArrayList<Integer>();
int n = A.length;
for (int i=0; i<n; i++) {
if (A[i]%2 == 0 ) {
list.add(A[i]);
} else {
list2.add(A[i]);
}
}
int[] result = new int[n];
int index = 0;
for (int j=0; j<list.size(); j++) {
result[index++] = list.get(j);
}
for (int j=0; j<list2.size(); j++) {
result[index++] = list2.get(j);
}
return result;
}
03 第二种解法
针对第一种解法，我们再简化下，不使用List存数据，我们分两次遍历处理A中的元素，第一次只要偶数元素，存入新数组result中，第二次只要奇数元素，存入新数组result中。
此解法的时间复杂度是O(N)，空间复杂度是O(N)。
public int[] sortArrayByParity2(int[] A) {
int n = A.length, index = 0;
int[] result = new int[n];
for (int i=0; i<n; i++) {
if (A[i]%2 == 0 ) {
result[index++] = A[i];
}
}
for (int j=0; j<n; j++) {
if (A[j]%2 != 0 ) {
result[index++] = A[j];
}
}
return result;
}
04 第三种解法
我们也可以只使用一个循环，不使用额外的数组，借助双指针来解题。
创建两个指针，一个从A的第一位开始，记为i，另外一个从A的最后一位开始，记为j。如果i对应的元素为奇数，且j对应的元素是偶数，那么就需要将两个元素互换，互换后，偶数排在了前面，奇数换到了后面。另外我们还需要让两个指针移动，以便遍历完所有元素，如果i对应的元素为偶数，就跳到下一个元素，同理，如果j对应的元素为奇数，就跳到前一个元素，直到i不小于j。
此解法的时间复杂度是O(N)，空间复杂度是O(1)。
public int[] sortArrayByParity3(int[] A) {
int i = 0, j = A.length-1;
while (i < j) {
if (A[i]%2 !=0 && A[j]%2 ==0) {
int tem = A[j];
A[j] = A[i];
A[i] = tem;
}
if (A[i]%2 ==0) {
i++;
}
if (A[j]%2 !=0) {
j--;
}
}
return A;
}
