您当前位置：首页 > php开源 > php教程 > 剑指offer 面试题14―调整数组顺序使奇数位于偶数前面

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

来源：程序员人生发布时间：2015-05-12 09:16:47 阅读次数：2945次

题目：

输入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]);//交换 } }

生活不易，码农辛苦
如果您觉得本网站对您的学习有所帮助,可以手机扫描二维码进行捐赠
程序员人生

------分隔线----------------------------

上一篇 JPA（三）：JPA+Hibernate 基础学习

下一篇 mysql学习笔记之十一（常用函数）

分享到:

------分隔线----------------------------

为码而活

积分：4237

15粉丝

7关注

栏目热点