剑指offer 面试题14―调整数组顺序使奇数位于偶数前面

题目:

输入1个整数数组,实现1个函数来调剂该数组中数组的顺序,使得所有奇数位于数组的前半部份,所有偶数位于数组的后半部份。


解法1:O(n^2)

从头扫描数组,每碰到1个偶数,拿出这个数字,并把位于这个数字后面的所有数字往前移动1位。挪完以后在数组的末尾有1个空位,这时候把该偶数放入这个空位中。

由于每碰到1个偶数就需要移动O(n)个数字,因此总的时间复杂度是O(n^2).


解法2:O(n)

类似快排,两个指针,1个指向数组头,只向后移动,1个指向数组尾,只向前移动。如果第1个指针指向的数字是偶数,并且第2个指针指向的数字是奇数,交换两数。

void foo(int a[],int left,int right)
{
if(left>right)
return;
int i,j;
i=left;
j=right;
while(i!=j)
{
while(a[j]%2==0&&i<j) j–;
while(a[i]%2!=0&&i<j) i++;

if(i<j)
swap(a[i],a[j]);//交换
}
}

波比源码 – 精品源码模版分享 | www.bobi11.com
1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长!
2. 分享目的仅供大家学习和交流,您必须在下载后24小时内删除!
3. 不得使用于非法商业用途,不得违反国家法律。否则后果自负!
4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解!
5. 如有链接无法下载、失效或广告,请联系管理员处理!
6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需!
7. 本站源码并不保证全部能正常使用,仅供有技术基础的人学习研究,请谨慎下载
8. 如遇到加密压缩包,请使用WINRAR解压,如遇到无法解压的请联系管理员!

波比源码 » 剑指offer 面试题14―调整数组顺序使奇数位于偶数前面

发表评论

Hi, 如果你对这款模板有疑问,可以跟我联系哦!

联系站长
赞助VIP 享更多特权,建议使用 QQ 登录
喜欢我嘛?喜欢就按“ctrl+D”收藏我吧!♡