小白解法:
思路,若是选出奇偶,然后插到前面,太麻烦,后续还要移动后面的数字,考虑另建数组,选出奇偶放入。
我的解法:先找奇数,放入数组,再找偶数放入数组,这样做法时间复杂度O(2N),空间复杂度O(N)。
代码如下:
class Solution { public: /** * 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可 * * * @param array int整型vector * @return int整型vector */ vector<int> reOrderArray(vector<int>& array) { // write code here vector<int>ou; int l = array.size(); for(int i=0;i<l;i++){ if(array[i]%2 == 1) ou.push_back(array[i]); } for(int i=0;i<l;i++){ if(array[i]%2 == 0) ou.push_back(array[i]); } return ou; } };
后来看到别人的解法,瞬间觉得自己好差劲,既然偶数在后,奇数在前,设置首尾指针不就好了,首指针找奇数,放到前面;尾指针找偶数,从后往前放。这样只需要遍历一次数组就可。