- 题目描述：
-
输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
- 输入：
-
每个输入文件包含一组测试案例。
对于每个测试案例，第一行输入一个n，代表该数组中数字的个数。接下来的一行输入n个整数。代表数组中的n个数。
- 输出：
-
对应每个测试案例，
输入一行n个数字，代表调整后的数组。注意，数字和数字之间用一个空格隔开，最后一个数字后面没有空格。
- 样例输入：
-
51 2 3 4 5
- 样例输出：
-
1 3 5 2 4
对于普通的交换顺序，只要设两个指针分别从头跟尾扫描，当分别遇到不符合条件的位置时停止，然后交换位置，这样只要时间O(n)，空间O(1)，但是这样做会改变原来的顺序，要保持原来的位置，可以借用一个队列，先将一类数放到正确的位置上，再将队列里的数放到剩下的位置。时间仍为O(n)，但是要用额外空间，大小取决于输入。最坏情况下空间为O(n)。
1 #include2 #include 3 #include 4 #include 5 using namespace std; 6 7 int main() { 8 //freopen("1516.input", "r", stdin); 9 vector v;10 queue q;11 int n;12 while (scanf("%d", &n) != EOF) {13 v.resize(n);14 for (int i = 0; i < n; ++i) {15 scanf("%d", &v[i]);16 }17 int count = 0;18 for (int i = 0; i < n; ++i) {19 if (v[i] % 2 == 1) {20 v[i - count] = v[i];21 } else {22 ++count;23 q.push(v[i]);24 }25 }26 for (int i = n - count; i < n; ++i) {27 v[i] = q.front();28 q.pop();29 }30 for (int i = 0; i < n; ++i) {31 (i == n - 1) ? printf("%d\n", v[i]) : printf("%d ", v[i]);32 }33 }34 return 0;35 }36 37 /**************************************************************38 Problem: 151639 User: hupo25040 Language: C++41 Result: Accepted42 Time:90 ms43 Memory:2048 kb44 ****************************************************************/
附上通过交换元素不保持相对顺序的代码。
#include#include #include using namespace std;int main() { //freopen("1516.input", "r", stdin); int n; vector v; while (scanf("%d", &n) != EOF) { v.resize(n); for (int i = 0; i < n; ++i) { scanf("%d", &v[i]); } int s = 0, e = n - 1, t; while (s < e) { while (!v[s] & 1 && s < e) ++s; while (v[s] & 1 && s < e) --e; t = v[s]; v[s] = v[e]; v[e] = t; } for (int i = 0; i < n; ++i) { (i == n - 1) ? printf("%d\n", v[i]) : printf("%d ", v[i]); } } return 0;}