加入收藏 | 设为首页 | 会员中心 | 我要投稿 李大同 (https://www.lidatong.com.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 站长学院 > PHP教程 > 正文

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

发布时间:2020-12-13 20:09:34 所属栏目:PHP教程 来源:网络整理
导读:题目: 输入1个整数数组,实现1个函数来调剂该数组中数组的顺序,使得所有奇数位于数组的前半部份,所有偶数位于数组的后半部份。 解法1:O(n^2) 从头扫描数组,每碰到1个偶数,拿出这个数字,并把位于这个数字后面的所有数字往前移动1位。挪完以后在数组的

题目:

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


(编辑:李大同)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    推荐文章
      热点阅读