题目难度:中等
题目内容:输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
题目分析:
给定一个数组,要求奇数在前,偶数在后,并且相对位置不变,首先应该会想到类似排序的思想来交换,但是会出现什么问题,如图所示
下面给出一个较为清楚,代码简洁的思路,定义一个数组,第一次遍历加进去所有奇数,第二次遍历加进去所以偶数,这时就完成了题目要求,证明如下
算法1(辅助数组加遍历)
下面给出代码
class Solution { public: vector<int> reOrderArray(vector<int>& array) { // write code here vector<int>ans;//记录答案 for(int i=0;i<array.size();i++) if(array[i]%2==1)ans.push_back(array[i]); //第一次遍历记录所有奇数 for(int i=0;i<array.size();i++) if(array[i]%2==0)ans.push_back(array[i]); //第二次遍历记录所有偶数 return ans; //返回数组 } };
下面给出一种更为巧妙地解法
算法2
class Solution { public void swap(int a, int b, int[] nums){ int temp = nums[a]; nums[a] = nums[b]; nums[b] = temp; } public int[] exchange(int[] nums) { int l = 0; int r = nums.length - 1; while(l < r){ if((nums[l] & 1) == 1 && (nums[r] & 1) == 0) {l++; r--;} else if((nums[l] & 1) == 0 && (nums[r] & 1) == 1) swap(l++, r--, nums); else if((nums[l] & 1) == 1) l++; else r--; } return nums; } }