算法-调整数组顺组使奇数位于偶数前面

题目: 输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有奇数位于数组的前半部分,偶数位于数组的后半部分。

解题思路: 比如我们有一个这样的数组:

数组的长度为10,最后能够实现前面4个数字是奇数,后面6个数字是偶数就好了,前面奇数的排序后后面偶数的排序没有要求,比如:

为啥数组里面有两个2呢?这是为了后面介绍是更方便的说明指针如何移动。

为了实现这个任务,一个最简单、粗暴、直接的方法就是从头遍历数组,如果发现是偶数,就拿出这个数并把该数字后面的元素全部向前移动一位,把这个数放到数组的最后一位。

由于我们并不知道数组中有几个奇数,有几个偶数,所以我们不得不遍历整个数组,所以这个算法的时间复杂度为O(n^2)

好在我们有更好的方式解决这个问题,管理两个指针p1和p2,p1初始位置指向数组中第一个数,p2初始位置指向数组中最后一个数,如果恰好p1指向地址内的是偶数,p2指向的地址内是奇数,那么就交换数值,移动指针,做下一次判断。举个例子:

p1指向0,p2指向9,两个数值交换,并且p1向后走1,p2向前走1;此时p1指向2,p2指向8,8就是偶数不需要交换,所以p1不动(等待p2指向奇数和它交换),p2向前走一步;此时p2指向7,两个数值交换并且p1向后走1,p2向前走1,重复上面的步骤:

此时p1指向3,p2指向4,不需要交换并且p1向后走1,p2向前走1:

p1跑到p2的后面了,表明所有的奇数都在偶数的前面了。

我们从上面的例子可以总结出指针移动的一些规律: p1只向后走,p2只向前走,其p1在p2后面时结束; 每次数值交换后p1,p2各走一步; p1指向偶数时如果p2满足条件则交换,不满足则保持不动,p2同理。 根据上面的分析,我们就可以写代码了。

代码实现

void ReorderOddEven(int *pData, unsigned int length)
{
    if(pData == NULL || length == 0)
        return;

    int *pBegin = pData;
    int *pEnd = pData + length - 1;

    while(pBegin < pEnd)
    {
        while(pBegin < pEnd && (*pBegin & 0x1) != 0)
            pBegin ++;

        while(pBegin < pEnd && (*pEnd & 0x1) == 0)
            pEnd --;

        if(pBegin < pEnd)
        {
            int temp = *pBegin;
            *pBegin = *pEnd;
            *pEnd = temp;
        }
    }
}

1.显然所有的操作都应该有一个大前提,p1(pBegin)在p2(pEnd)的前面:while(pBegin < pEnd),由于数组是连续存储,后面的地址一定比前面的大,代码就是在利用这个特点控制何时终止。 2.代码判断奇偶数:0x1—00000001,按位与操作。 3.循环内if判断的作用:显然两个指针从while退出之后,pBegin指向奇数,pEnd指向偶数,但是到了最后一步,就不能再交换了。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏编程坑太多

程序猿真的觉得写代码比女朋友重要吗?

693
来自专栏iOSer成长记录

RunLoop 源码阅读

1755
来自专栏小壮和前端

键盘事件 和键码

771
来自专栏HT

基于HTML5 Canvas 实现地铁站监控

伴随国内经济的高速发展,人们对安全的要求越来越高。为了防止下列情况的发生,您需要考虑安装安防系统: 提供证据与线索:很多工厂银行发生偷盗或者事故相关机关可以根据...

1935
来自专栏xx_Cc的学习总结专栏

iOS底层原理总结 - RunLoop

4737
来自专栏陈满iOS

iOS开发·RunLoop源码与用法完全解析(输入源,定时源,观察者,线程间通信,端口间通信,NSPort,NSMessagePort,NSMachPort,NSPortMessage)

OSX / iOS 系统中,提供了两个这样的对象:NSRunLoop 和 CFRunLoopRef。

982
来自专栏xx_Cc的学习总结专栏

iOS-RunLoop充满灵性的死循环

3788
来自专栏娱乐心理测试

多线程与NSTimer

1315
来自专栏软件开发 -- 分享 互助 成长

享元模式

一、简介 1、享元模式运用共享技术有效地支持大量细粒度的对象。 2、享元模式是为了减少同种类的实例化,以达到节省内存的目的。 3、类成员函数 抽象享元类(Fly...

1789
来自专栏哈雷彗星撞地球

RunLoop总结:RunLoop基础知识

没有实际应用场景,很难理解一些抽象空洞的东西,所以前面几篇文章先介绍了RunLoop的几个使用场景。 另外AsyncDisplayKit中也有大量使用RunL...

1062

扫码关注云+社区