Sort Array By Parity 原
Sort Array By Parity 原
青木
发布于 2018-10-09 15:59:58
发布于 2018-10-09 15:59:58
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;
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录