Sort Array By Parity
AC-17ms.
按照《算法导论》排序一章的一些概念,第二种可以称为是原址的(in-place)。
First Try:
用了另一个数组来保存结果,如果是奇数进行swap操作,同时在else中还要维护偶数的位置正确性。
class Solution {
public int[] sortArrayByParity(int[] A) {
int[] result = new int[A.length];
for (int i = 0,tmp = 0; i < A.length; i++) {
if (A[i] % 2 == 1) {
result[A.length - tmp - 1] = A[i];
tmp ++;
} else {
result[i - tmp] = A[i];
}
}
return result;
}
}
提交后瞄了眼,发现可以只操作原数组,改了一下,这次只需要将even数据移到前面即可。
for (int i = 0,evenIndex = 0; i < A.length; i++) {
if (A[i] % 2 == 0) {
int tmp = A[i];
A[i] = A[evenIndex];
A[evenIndex] = tmp;
evenIndex ++;
}
}
System.err.println(System.nanoTime() - start + "ms.");
return A;
网友评论