leetcode数组array标签题目更新中

905. Sort Array By Parity（easy）

题目理解：
一个数组中全是非负数，现在要我们把偶数放在前面，奇数放在偶数之后

首先想到的做法：声明一个新的 vector，扫描 A 两遍，第一遍插入偶数，第二遍插入奇数，返回新的 vector
可能优化方向：

• 扫描一遍
• 不分配新空间

于是想到了新的做法：用两个指针标记位置，两个指针分别从前往后和从后往前扫描
比较两个指针所指的数据有 4 种情况：

情况	对应操作
前奇后偶	交换位置，i 向后移，j 向前移
前偶后奇	不用交换，i 往后移，j 往前移
前后全是偶数	不用交换，i 往后移
前后全是奇数	不用交换，j 往前移

其实这种做法的本质就是利用两个指针在 O(N)时间里达到了和之前扫描两次同样的效果，并且维护了原数组，就不用再分配新的空间了，这也是一种比较常用的做法。
在实际代码里我对 i，j 移动的时机做了一些改动，结果是一样的，但是看起来可能更简单，也可以分成四种情况逐一用 if…else if 来写。
accept 代码

class Solution {
public:
    vector<int> sortArrayByParity(vector<int>& A) {int i = 0, j = A.size() - 1;
        int n = A.size();
        while (i < j)
        {if (A[i] % 2 != 0 && A[j] % 2 != 1)
                swap(A[i++], A[j--]);
            if (A[i] % 2 == 0)
                i++;
            if (A[j] % 2 == 1)
                j--;
        }
        return A;
    }

};

重点：

• 两个指针