按奇偶排序数组 II - Sort Array By Parity II

【双指针】

``````给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。

``````

Example:

``````输入：[4,2,5,7]

``````

1. `2 <= A.length <= 20000`
2. `A.length % 2 == 0`
3. `0 <= A[i] <= 1000`

Solutions

Solution 【双指针】 ( 7ms) O(N)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 `````` ``````class Solution { public int[] sortArrayByParityII(int[] A) { int idx_even = 0; int idx_odd = 1; int length = A.length; while (idx_even < length && idx_odd < length) { while (idx_even < length && A[idx_even] % 2 == 0) { idx_even += 2; } while (idx_odd < length && A[idx_odd] % 2 == 1) { idx_odd += 2; } if (!(idx_even < length && idx_odd < length)) { break; } int tmp = A[idx_even]; A[idx_even] = A[idx_odd]; A[idx_odd] = tmp; idx_even += 2; idx_odd += 2; } return A; } } ``````

Solution ( 5ms)

 `````` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 `````` ``````class Solution { public int[] sortArrayByParityII(int[] A) { int j = 1; for (int i = 0; i < A.length; i += 2) { if ((A[i] & 1) != 0) { while ((A[j] & 1) != 0) { j += 2; } int tmp = A[i]; A[i] = A[j]; A[j] = tmp; } } return A; } } ``````