922. 按奇偶排序数组 II

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

对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    vector<int> sortArrayByParityII(vector<int>& A) {
        int i = 0;
        int len = A.size();
        int j = 1;
        while(1){
            while(i < len && (A[i] & 1) == 0) i+=2;
            while(j < len && (A[j] & 1) != 0) j+=2;
            if(i >= len || j >= len) break;
            std::swap(A[i],A[j]);
            i+=2;
            j+=2;
        }
        return A;
    }
    
};

思路：

设置两个指针。
一个指针只走奇数下标，一个指针只走偶数下标。
当碰到不符合条件（奇数下标的值不是奇数，偶数下标的值不是偶数）就停下并交换两个值，之后接着走，直到指针越界为止。

看评论有人用栈或者另外准备两个数组的，速度比原地交换还快，不知道为什么。实现也比较简单，就不赘述了。