Zero Lee的专栏

百度的面试题解答

给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。
要求:空间复杂度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 

posted on 2011-03-11 19:10 Zero Lee 阅读(367) 评论(0)  编辑 收藏 引用 所属分类: Data structure and algorithms


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理