Given an array A of non-negative integers, half of the integers in A are odd, and half of the integers are even.

Sort the array so that whenever A[i] is odd, i is odd; and whenever A[i] is even, i is even.

You may return any answer array that satisfies this condition.

Example 1:

Input: [4,2,5,7]
Output: [4,5,2,7]
Explanation: [4,7,2,5], [2,5,4,7], [2,7,4,5] would also have been accepted.

Note:

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

按奇偶排序数组 II。

题目即是题意。这道题跟版本一差不多，也是对数组进行有条件的排序和整理。这道题的思路是追击型的双指针，两个指针分别判断奇数下标和偶数下标上的数字是不是符合条件，若两边都找到不符合的下标则swap。

时间O(n)

空间O(1)

Java实现

 1 class Solution {
 2     public int[] sortArrayByParityII(int[] A) {
 3         int i = 0;
 4         int j = 1;
 5         int n = A.length;
 6         while (i < n && j < n) {
 7             while (i < n && A[i] % 2 == 0) {
 8                 i += 2;
 9             }
10             while (j < n && A[j] % 2 == 1) {
11                 j += 2;
12             }
13             if (i < n && j < n) {
14                 swap(A, i, j);
15             }
16         }
17         return A;
18     }
19 
20     private void swap(int[] A, int i, int j) {
21         int temp = A[i];
22         A[i] = A[j];
23         A[j] = temp;
24     }
25 }

 

相关题目

75. Sort Colors

905. Sort Array By Parity

922. Sort Array By Parity II

LeetCode 题目总结