905. Sort-Array-By-Parity

difficulty: Easy

section pre{ background-color: #eee; border: 1px solid #ddd; padding:10px; border-radius: 5px; }

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.

Note:

1. 1 <= A.length <= 5000

2. 0 <= A[i] <= 5000

Method One

这是之前写的，其实已经很好了，但是还是不如最好的好。可以看出来，有一定重复的代码。

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int index = 0;
        for(int i = 0; i < A.length; i++){
            if( A[i]%2 == 0){
                swap(A, index++, i);
            }
        }
        return A;
    }
    public void swap(int[] arr, int i, int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}
​

改进之后的： 其实核心都是快速排序的partition代码。

class Solution {
    public int[] sortArrayByParity(int[] A) {
        int left = 0;
        int right = A.length - 1;
        while( left <= right ){
            if( A[right] % 2 == 0 ){
                swap(A, left++, right);
            }else{
                right--;
            }
        }
        return A;
    }
    public void swap(int[] arr, int i, int j){
        if( i == j){
            return;
        }
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}