https://leetcode-cn.com/problems/sort-array-by-parity-ii/
给定一个非负整数数组 A， A 中一半整数是奇数，一半整数是偶数。
对数组进行排序，以便当 A[i] 为奇数时，i 也是奇数；当 A[i] 为偶数时， i 也是偶数。
你可以返回任何满足上述条件的数组作为答案。
示例：
输入：[4,2,5,7]
输出：[4,5,2,7]
解释：[4,7,2,5]，[2,5,4,7]，[2,7,4,5] 也会被接受。
提示：
2 <= A.length <= 20000
A.length % 2 == 0
0 <= A[i] <= 1000
小菜鸡的尝试：
只是做出还是简单的，给出的向量是一半偶数一半奇数，我们的需求是偶数放在结果向量的偶数位，奇数放在结果向量的奇数位。那么我们可以遍历给出的向量，判断每个数依次是偶数还是奇数，用两个变量odd和even记录上一次用到的偶数位置和奇数位置，只需要将偶数/奇数，插入当前偶数位置/奇数位置，再将使用过的偶数位置/奇数位置下移两个即可。
期间因为比较菜还是遇到了一点数据结构上的问题。发现不能直接向空向量插入元素，会溢出。挺疑惑的，因为觉得向量不是可以自己expand嘛，为什么会溢出呢？但其实vector是不能通过索引扩容的，不过使用push_back()是会扩容的。那么我们就需要手动扩容，涉及到两个方法：resize() 和 reserve()。容器调用resize()函数后，所有的空间都已经初始化了，所以可以直接访问。而reserve()函数预分配出的空间没有被初始化，所以不可访问。
1 class Solution { 2 public: 3 vector<int> sortArrayByParityII(vector<int>& A) { 4 vector<int> result; 5 int size = A.size(); 6 int odd = 1; 7 int even = 0; 8 result.resize(size); 9 for (int i = 0; i < size; i ++) { 10 if (A[i] % 2 == 0) { 11 result[even] = A[i]; 12 even = even + 2; 13 } else { 14 result[odd] = A[i]; 15 odd = odd + 2; 16 } 17 } 18 return result; 19 } 20 };
不过也很想知道大佬们有没有更好的办法
膜拜大佬代码：
看到了一个挺不错的思路：因为要求偶数位放偶数，奇数位放奇数，那么原来就在偶数位的偶数，原来就在奇数位的奇数是可以不面临操作的。
于是我们以偶数为视角（奇数同理），从下标0开始遍历，每次递增2。如果当前访问的（必定是偶数位）不是偶数，那么就找到待操作的下一个在奇数位不是奇数的数字，交换 。
1 class Solution { 2 public: 3 vector<int> sortArrayByParityII(vector<int>& A) { 4 int j = 1; 5 int size = A.size(); 6 for (int i = 0; i < size; i += 2) { 7 if (A[i] % 2 == 1) { 8 while (A[j] % 2 == 1) { 9 j += 2; 10 } 11 int tmp = A[i]; 12 A[i] = A[j]; 13 A[j] = tmp; 14 } 15 } 16 return A; 17 } 18 };