前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >专栏 >算法-调整数组顺组使奇数位于偶数前面

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

作者头像
chaibubble
发布于 2018-01-02 03:42:57
发布于 2018-01-02 03:42:57
83700
代码可运行
举报
运行总次数:0
代码可运行

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

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

数组的长度为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同理。 根据上面的分析,我们就可以写代码了。

代码实现

代码语言:javascript
代码运行次数:0
运行
AI代码解释
复制
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指向偶数,但是到了最后一步,就不能再交换了。

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2017-08-07 ,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
暂无评论
推荐阅读
Django ORM的简单总结
我们继续昨天的内容使用Oracle中的emp,dept来学习Django ORM,今天做一些总结和扩展,希望你能有所收获。 先来说下两张表emp,dept。 emp表的数据如下: dept表的数据如下
jeanron100
2018/03/22
1.2K0
Django ORM的简单总结
Django-model进阶(中介模型,查询优化,extra,整体插入)
QuerySet 可切片 使用Python 的切片语法来限制查询集记录的数目 。它等同于SQL 的LIMIT 和OFFSET 子句。 1 >>> Entry.objects.all()[:5]      # (LIMIT 5) >>> Entry.objects.all()[5:10] # (OFFSET 5 LIMIT 5) 不支持负的索引(例如Entry.objects.all()[-1])。通常,查询集 的切片返回一个新的查询集 —— 它不会执行查询。 可迭代 ar
用户1214487
2018/01/24
1.7K0
django select_related和prefetch_related的用法与区别
在前面教程中小编我已经介绍了Django的Queryset特性及高级使用技巧以及Queryset的aggregate和annotate方法。这些技巧和方法都是为了减少对数据库的访问次数和对内存的占用,从而提升网站性能。今天我们再来学习两个非常重要的查询方法select_related和prefetch_related方法,看看如何使用它们避免不必要的数据库查询。高手过招,只差分毫。专业和业余之前的区别就在细节的处理上。为了让大家更直观地看到这两个方法的作用,我们将安装使用django-debug-toolbar这个流行的Django第三方包。
kirin
2021/05/08
1.4K0
Django学习-第八讲:django ORM数据库查询,修改等操作
查找是数据库操作中一个非常重要的技术。查询一般就是使用filter、exclude以及get三个方法来实现。我们可以在调用这些方法的时候传递不同的参数来实现查询需求。在ORM层面,这些查询条件都是使用field+__+condition的方式来使用的。
小海怪的互联网
2019/10/08
5440
django 菜鸟篇+进阶篇[通俗易懂]
django自带web server, 故django开发的项目可以独立的运行,也可以安置在apache(+mod_python)下运行
全栈程序员站长
2022/10/04
2K0
django--ORM的单表操作
它的作用相当于 在该app下建立 migrations目录,并记录下你所有的关于modes.py的改动,比如0001_initial.py, 但是这个改动还没有作用到数据库文件
py3study
2018/08/03
1K0
Django之ORM其他骚操作
Django ORM执行原生SQL # extra # 在QuerySet的基础上继续执行子语句 # extra(self, select=None, where=None, params=None, tables=None, order_by=None, select_params=None) # select和select_params是一组,where和params是一组,tables用来设置from哪个表 # Entry.objects.extra(select={'new_id': "selec
人生不如戏
2018/04/12
1K0
Django(19)QuerySet API[通俗易懂]
我们通常做查询操作的时候,都是通过模型名字.objects的方式进行操作。其实模型名字.objects是一个django.db.models.manager.Manager对象,而Manager这个类是一个“空壳”的类,他本身是没有任何的属性和方法的。他的方法全部都是通过Python动态添加的方式,从QuerySet类中拷贝过来的。示例图如下:
全栈程序员站长
2022/09/16
7660
Django(19)QuerySet API[通俗易懂]
Django——model基础
ORM 映射关系:     表名 <-------> 类名 字段 <-------> 属性     表记录 <------->类实例对象 创建表(建立模型) 实例:我们来假定下面这些概念,字段和关系 作者模型:一个作者有姓名和年龄。 作者详细模型:把作者的详情放到详情表,包含生日,手机号,家庭住址等信息。作者详情模型和作者模型之间是一对一的关系(one-to-one) 出版商模型:出版商有名称,所在城市以及email。 书籍模型: 书籍有书名和出版日期,一本书可能会有多个作者,一个作
用户1214487
2018/01/24
1.2K0
Django——model基础
Django学习笔记之Django ORM相关操作
<!-- p.p1 { margin: 0.0px 0.0px 0.0px 0.0px; font: 11.0px "PingFang SC"; color: #000000 } span.s1 { } span.s2 { font: 11.0px Helvetica } -->
Jetpropelledsnake21
2019/02/15
3.7K0
Django(17)orm查询操作[通俗易懂]
查找是数据库操作中一个非常重要的技术。查询一般就是使用filter、exclude以及get三个方法来实现。我们可以在调用这些方法的时候传递不同的参数来实现查询需求。在ORM层面,这些查询条件都是使用field+__+condition的方式来使用的。以下将那些常用的查询条件来一一解释。
全栈程序员站长
2022/09/19
1.1K0
Django学习-第十讲(上):QuerySet API 学习
我们通常做查询操作的时候,都是通过模型名字.objects的方式进行操作。其实模型名字.objects是一个django.db.models.manager.Manager对象,而Manager这个类是一个“空壳”的类,他本身是没有任何的属性和方法的。他的方法全部都是通过Python动态添加的方式,从QuerySet类中拷贝过来的
小海怪的互联网
2019/10/08
6140
Django学习-第十讲(上):QuerySet API 学习
django 1.8 官方文档翻译: 2-2-1 执行查询
一旦你建立好数据模型之后,django会自动生成一套数据库抽象的API,可以让你执行增删改查的操作。这篇文档阐述了如何使用这些API。关于所有模型检索选项的详细内容,请见数据模型参考。
ApacheCN_飞龙
2022/11/27
4.5K0
Django---ORM操作大全
前言 Django框架功能齐全自带数据库操作功能,本文主要介绍Django的ORM框架 到目前为止,当我们的程序涉及到数据库相关操作时,我们一般都会这么搞: 创建数据库,设计表结构和字段 使用 MySQLdb 来连接数据库,并编写数据访问层代码 业务逻辑层去调用数据访问层执行数据库操作 ORM是什么?:(在django中,根据代码中的类自动生成数据库的表也叫--code first) ORM:Object Relational Mapping(关系对象映射) 类名对应------》数据库中的表名 类属性
用户1214487
2018/01/24
7K1
Django---ORM操作大全
Django之QuerySet详解
在内部,创建、过滤、切片和传递一个QuerySet不会真实操作数据库,在你对查询集提交之前,不会发生任何实际的数据库操作。可以使用下列方法对QuerySet提交查询操作:
菲宇
2022/12/21
2.5K0
ORM常用操作
对于ForeignKey对象,clear()和remove()方法仅在null=True时存在
全栈程序员站长
2022/07/21
2.1K0
Django笔记(十二)连表查询之性能提升
就是通过一个字段点出来的。循环获取数据,再获取外键里面的数据的时候,会再次的执行sql语句进行数据库的查询。
一写代码就开心
2021/11/15
9110
Django笔记(十二)连表查询之性能提升
ORM初识和数据库操作
这样写上以后django会默认的就去链接数据库,这时你会看到报错了,那么解决的办法就是下面的这样
全栈程序员站长
2022/07/21
2.6K0
05.Django基础五之django模型层(一)单表操作
      创建名为book的app,在book下的models.py中创建模型:
changxin7
2019/09/29
3.1K0
python 终级篇 django --
                                   一般操作                                             
py3study
2020/01/19
2.9K0
python 终级篇 django --
相关推荐
Django ORM的简单总结
更多 >
领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档