给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。
要求:空间复杂度O(1),时间复杂度为O(n)。
1 bool func(int n)
2 {
3 return (n&1)==0; // n%2 is more expensive
4 }
5
6 void group_oddeven(std::vector<int>& a, bool (*func)(int))
7 {
8 int i = 0, j = a.size()-1;
9 int buf = 0;
10 while (i < j) {
11 if (!func(a[i])) // odd, move forward
12 { i++; continue; }
13 if (func(a[j])) // even, move backward
14 { j--; continue; }
15
16 std::swap(a[i++], a[j--]);
17 }
18 }
19