leetcode905(按奇偶排序数组)–Java语言实现

求：

给定一个非负整数数组 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

题目链接： https://leetcode-cn.com/problems/sort-array-by-parity/

解：

双指针

与快速排序的思想相似，利用2个指针i和j，初始时i指向数组第一个元素，j指向数组最后一个元素。然后i向后找奇数，j向前找偶数，当i找到奇数且j找到偶数时，如果i<j，则交换i和j指向的值。重复整个过程，直到i和j相遇。

时间复杂度：O(N)

空间复杂度：O(1)

public int[] sortArrayByParity(int[] A) {
    int i = 0, j = A.length - 1;
    while (i < j) {
        while (i < j && (A[i] & 1) == 0) ++i;
        while (i < j && (A[j] & 1) == 1) --j;
        if(i<j){
            A[i] += A[j];
            A[j] = A[i] - A[j];
            A[i] -= A[j];
            ++i;
            --j;
        }
    }
    return A;
}