题解 | #调整数组顺序使奇数位于偶数前面(二)#
调整数组顺序使奇数位于偶数前面(二)
https://www.nowcoder.com/practice/0c1b486d987b4269b398fee374584fc8?tpId=265&&tqId=39274&rp=1&ru=/ta/coding-interviews-all&qru=/ta/coding-interviews-all/question-ranking
题意：
输入一个长度为 n 整数数组，数组里面可能含有相同的元素，实现一个函数来调整该数组中数字的顺序，
使得所有的奇数位于数组的前面部分，所有的偶数位于数组的后面部分，
对奇数和奇数，偶数和偶数之间的相对位置不做要求。
方法一：
双指针
思路：利用双指针，左指针找偶数，右指针找奇数。
最后交换左右指针的数。
一直循环，直到左右指针相遇。
class Solution {
public:
vector<int> reOrderArrayTwo(vector<int>& array) {
int n=array.size();
int i=0,j=n-1;
while(i<j){//循环
while(i<j&&array[i]%2==1){//找偶数
i++;
}
while(i<j&&array[j]%2==0){//找奇数
j--;
}
swap(array[i],array[j]);//交换
}
return array;
}
};
时间复杂度：%2C%E5%8F%8C%E6%8C%87%E9%92%88%E9%81%8D%E5%8E%86%E6%95%B4%E4%B8%AA%E6%95%B0%E7%BB%84%E3%80%82)
空间复杂度：%2C%E5%B8%B8%E6%95%B0%E7%BA%A7%E5%88%AB%E5%AD%98%E5%82%A8%E7%A9%BA%E9%97%B4%E3%80%82)
方法二：
计数+双指针
思路：
遍历一遍数组，对奇数个数计数。
初始化左边奇数区间的范围，右边偶数区间的范围。
再利用双指针实现。
class Solution {
public:
vector<int> reOrderArrayTwo(vector<int>& array) {
int n=array.size();
int cnt=0;//奇数个数
for(int i=0;i<n;i++){
if(array[i]%2)
cnt++;
}
int x=0,y=cnt;
while(x<cnt&&y<n){//循环
while(x<cnt&&(array[x]%2))//寻找偶数
x++;
while(y<n&&(array[y]%2==0))//寻找奇数
y++;
if(x<cnt&&y<n)
swap(array[x],array[y]);//交换
}
return array;
}
};
时间复杂度：空间复杂度：
