牛客 小米 数组操作 deque或双指针

题目描述
输入一个无序整数数组，调整数组中数字的顺序， 所有偶数位于数组的前半部分，使得所有奇数位于数组的后半部分。
要求时间复杂度为O(n)。
输入描述:

给定无序数组。
长度不超过1000000。

输出描述:

所有偶数位于数组的前半部分，所有奇数位于数组的后半部分。
如果有多个答案可以输出任意一个正确答案。

示例1
输入
复制

2 4 5 7 8 1

输出
复制

2 4 8 7 5 1

双端队列 $deque$deque

deque<int> q;
int x;
while(~scanf("%d ", &x)) {
    if(x & 1) q.push_back(x);
    else q.push_front(x);
}
int p = 0;
while(!q.empty()) {
    if(p ++) printf(" ");
    printf("%d", q.front());
    q.pop_front();
}

双指针

while(~scanf("%d ", &m)) a[++n] = m;
int lef = 1, rig = n;
while(lef < rig) {
	if(a[lef] & 1) {
		swap(a[lef], a[rig]);
		rig --;
	} else 
		lef ++;
}
int p;
for(int i=1; i<=n; i++) {
	if(p ++) printf(" ");
	printf("%d", a[i]);
}