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

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

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

数组的长度为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 条评论
登录 后参与评论

相关文章

来自专栏二进制文集

FastJSON 源码分析

Fastjson是一个Java语言编写的高性能功能完善的JSON库。它采用一种“假定有序快速匹配”的算法,把JSON Parse的性能提升到极致,是目前Java...

1692
来自专栏算法修养

PAT 1040

字符串APPAPT中包含了两个单词“PAT”,其中第一个PAT是第2位(P),第4位(A),第6位(T);第二个PAT是第3位(P),第4位(A),第6位(T)...

3287
来自专栏行者常至

020.Java的反射机制

JAVA反射机制是在运行状态中, 对于任意一个类,都能够知道这个类的所有属性和方法; 对于任意一个对象,都能够调用它的任意方法和属性; 这种动态获取信息以...

711
来自专栏猿人谷

获取对象属性类型、属性名称、属性值的研究:反射和JEXL解析引擎

先简单介绍下反射的概念:java反射机制是在运行状态中,对于任意一个类,都能够知道这个类的所有属性和方法;对于任意一个对象,都能够调用它的任意方法和属性;这种动...

1.2K5
来自专栏Coding迪斯尼

java开发编译器:把C语言的循环指令编译成java字节码

1513
来自专栏Spring相关

第12章—使用NoSQL数据库—使用MongoDB+Jpa操作数据库

SpringData还提供了对多种NoSQL数据库的支持,包括MongoDB;neo4j和redis.他不仅支持自动化的repository,还支持基于模板的数...

732
来自专栏鸿的学习笔记

简单定义Python和Scala的类和对象

在现代编程语言里,类和对象都是绕不过的话题。对象这个概念可以是生活的抽象,为了更好的理解使用书来做比喻,每一本书都是一个对象,也就是一个实例,书本身具有的页码等...

731
来自专栏数据之美

简化你的 java 字符串操作:Guava 之 CharMatcher 用法简介

对字符串的处理应该是编程活动中最频繁的操作了,而原生的 JDK 以及 Java 本身的语法特性使得在 Java 中进行字符串操作是一件极其麻烦的事情,如果你熟...

2708
来自专栏王硕

原 PostgreSQL源码中的List和ListCell的说明

3748
来自专栏算法修养

HDU 3333 Turing Tree (线段树)

Turing Tree Time Limit: 6000/3000 MS (Java/Others)    Memory Limit: 32768/32768...

3448

扫码关注云+社区