LeetCode 905题-按奇偶排序数组
零 题解
Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/sort-array-by-parity 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
给定一个非负整数的数组，返回一个数组，所有的奇数元素在后面。
题目没有要求时间复杂度，也没有要求返回数组中元素的顺序，只要所有的奇数元素在后面即可。
一 思路分析
- 1 新建1个和给定数组A类型一致，长度一致的数组；
- 2 遍历数组A，凡是元素是偶数的(%2==0)，就将其逐个插入到B；引入一个整型变量j=0，用于记录B数组的下标，每次插入一个新元素之后，j++；
- 3 再次遍历数组A，凡是元素是奇数的(%2！=0)，就将其逐个插入到B；继续沿用整型变量j，用于记录B数组的下标，每次插入一个新元素之后，j++；这样做的好处是：当A数组全是奇数元素的话，前面一次遍历A空跑了，j依然为0，可以继续从0开始插入全部的奇数元素；如果A数组中包含有任意个偶数元素的话，此时，j一定！=0，继续沿用j当作下标即可；
- 4 返回数组B即可。
二 代码实现
public class Solution{
public static int[] sortArrayByParity(int[] A){
int[] B = new int[A.length];
int j=0;
//插入偶数元素
for(int i=0;i<A.length;i++){
if(A[i]%2==0){
B[j++]=A[i];
}
}
//插入奇数元素
for(int i=0;i<A.length;i++){
if(A[i]%2!=0){
B[j++]=A[i];
}
}
return B;
}
public static void main(String[] args) {
int[] C = {2, 3, 5, 0, 99, 77, 44, 100};
int[] D = sortArrayByParity(C);
for (int k: D ) {
System.out.println(k);
}
}
}
//输出结果
2 0 44 100 3 5 99 77 三 复杂度分析
时间复杂度：O(n)，遍历数组A；
空间复杂度：O(n)，开辟了一个等长数组A的数组B，再加一个变量j；(我不是很确定这个分析角度是不是严谨)
四 提交
去掉sortArrayByParity()方法的static修饰符，去掉main()方法，提交即可。当然，LeetCode是支持带main()的代码。这里，就需要将main()中的调用方式，先new一个Solution的实例，再通过该实例调用sortArrayByParity()方法。
五 小结
开始的时候，我想到先把偶数元素插入到B之后，再开启一个新的变量k，用于记录插入奇数元素的下标。并且先判断j是否等于0：如果j==0,则k=j；如果j!=0，则k=j+1;后面，经过测试，发现有问题，数组长度会溢出报错。
问题的根源就是，数组的下标永远用于记录下一个待插入新元素的位置，也是数组中第一个元素为空的下标位置。
于是：无论j是否等于0，k都是应该等于j的。所以，最后就把临时变量k省略掉了。
第一版不够优雅的代码段如下：
public class Solution {
public static int[] sortArrayByParity(int[] A) {
int[] B = new int[A.length];
int j=0;
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 == 0) {
B[j++] = A[i];
}
}
int k=0;
if (j == 0) {
k = j;
} else {
k = j;
}
for (int i = 0; i < A.length; i++) {
if (A[i] % 2 != 0) {
B[k++] = A[i];
}
}
return B;
}
public static void main(String[] args) {
int[] C = {2, 3, 5, 0, 99, 77, 44, 100};
int[] D = sortArrayByParity(C);
for (int k: D ) {
System.out.print(k+" ");
}
}
}
