2019独角兽企业重金招聘Python工程师标准>>> 
Sort Array By Parity
Given an array A of non-negative integers, return an array consisting of all the even elements of A, followed by all the odd elements of A.
You may return any answer array that satisfies this condition.
Example 1:
Input: [3,1,2,4]
Output: [2,4,3,1]
The outputs [4,2,3,1], [2,4,1,3], and [4,2,1,3] would also be accepted.
说明
这个题目的意思是，将一个数列中的顺序调整为：前半部分为偶数，后半部分为奇数。除此之外，数列不必有序。
我用了快速排序的思路，从头和尾两边对数列进行遍历。
从左边开始，遇到奇数就停止遍历；然后从右边开始进行遍历，遇到偶数就停止遍历。 最后将这两个数交换顺序。
两边的遍历指针相遇的时候，整个工作结束。
MySolution
class Solution2
{
public:
vector<int> sortArrayByBarity(vector<int> &A)
{
int head = 0;
int rear = A.size()-1;
while(head < rear)
{
while((A[head]%2==0) && (head < rear)) head++;
while((A[rear]%2==1) && (head < rear)) rear--;
if(head < rear)
swap(A[head++],A[rear--]);
}
return A;
}
};
测试代码
#include<iostream>
#include<vector>
#include<map>
using namespace std;
class Solution2
{
public:
vector<int> sortArrayByBarity(vector<int> &A)
{
int head = 0;
int rear = A.size()-1;
while(head < rear)
{
while((A[head]%2==0) && (head < rear)) head++;
while((A[rear]%2==1) && (head < rear)) rear--;
if(head < rear)
swap(A[head++],A[rear--]);
}
return A;
}
};
int main(void)
{
vector<int> a;
a.push_back(100);
a.push_back(4);
a.push_back(200);
a.push_back(1);
a.push_back(3);
a.push_back(2)；
cout<<endl;
cout<<"Solution2 output:";
Solution2 s2;
s2.sortArrayByBarity(a);
for(int i = 0;i<a.size();i++)
cout <<" "<<a[i];
cout<<endl;
return 0;
}