【算法入门03】调整数组顺序使奇数位于偶数前面

【算法入门03】调整数组顺序使奇数位于偶数前面

核心考点：数组操作，排序思想的扩展使用

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。例如将数组{1, 2, 3, 4, 5, 6}调整为{1, 3, 5, 2, 4, 6}。

解析一：（若相对位置可变）

若是题目当中没有要求数组调整后奇数和奇数，偶数和偶数的相对位置不变，那么我们可以使用两个变量（left和right）来遍历数组，left从左往右寻找偶数，right从右往左寻找奇数，之后将left和right索引的元素进行交换。

如此进行下去，直到left和right错开为止。

class Solution {public: void reOrderArray(vector &array) { size_t left = 0, right = array.size() - 1; while (left < right) { while (left < right&&array[left] % 2 == 1) //left向右找偶数 { left++; } while (left < right&&array[right] % 2 == 0) //right向左找奇数 { right--; } swap(array[left], array[right]); //交换left和right索引的元素 } }};

解析二：（空间换时间）

既然题目要求数组调整后奇数和奇数，偶数和偶数的相对位置不变，那么我们可以使用一个辅助容器，先遍历一遍原数组，将数组当中的奇数依次尾插到容器当中。

然后再遍历一遍原数组，将数组当中的偶数也依次尾插到容器当中。

最后再将辅助容器当中的数据拷贝回原数组即可。

class Solution {public: void reOrderArray(vector &array) { vector temp; //辅助容器 //遍历数组将奇数尾插到temp容器当中 for (auto e : array) { if (e & 1) //是奇数 temp.push_back(e); } //遍历数组将偶数尾插到temp容器当中 for (auto e : array) { if (!(e & 1)) //是偶数 temp.push_back(e); } array = temp; //将temp容器赋值给array容器 }};

解析三：（时间换空间） 我们也可以选择将数组原地进行调整，调整过程大致如下： 首先定义三个变量：

变量 i：用于标记已经放好的奇数序列的后一个位置。变量 j：用于遍历数组，寻找奇数。变量 temp：用于暂时存储变量 j 找到的奇数。

变量 j 从左向右依次遍历数组，寻找奇数，找到奇数后将其暂时存储在temp变量当中，然后将变量 i 和变量 j 之间的数统一向后移动一位，最后再将temp变量当中存储的奇数放到 i 的位置，之后记得更新 i 的位置（因为已经放好的奇数序列此时增加了一个）。按此方法遍历数组，直到数组被遍历完毕为止。

动图演示如下：

class Solution {public: void reOrderArray(vector &array) { int i = 0; //标记已经放好的奇数序列的后一个位置 for (int j = 0; j < array.size(); j++) { if (array[j] & 1) //找到奇数 { int temp = array[j]; //先将这个奇数存储到temp变量当中 //将变量i和变量j之间的数统一向后移动一位 for (int k = j - 1; k >= i; k--) { array[k + 1] = array[k]; } array[i] = temp; //将temp变量当中存储的奇数放到i的位置 i++; //更新i的位置 } } }};

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。