调整数顺序使奇数位于偶数前面

2024-08-25 07:18

本文主要是介绍调整数顺序使奇数位于偶数前面,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

剑指offer_14 调整数顺序使奇数位于偶数前面


2018/05/14 星期一

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

思考三分钟。。。

一个简单的思路就是,顺序遍历数组,当我们碰到偶数的时候,就将该偶数后面的所有数字往前移一位,然后将该偶数放到数组移动后末尾挪出来的位置之中。整个时间复杂度 O(n2) O ( n 2 )

只完成基本功能的解法

这个题目要求把所有的奇数放在数组的前半部分,偶数放在数组的后半部分。也就是说,如果我们在扫描这个数组的时候,如果发现有偶数在奇数的前面,我们就可以交换他们的顺序。

因此,可以维护两个指针,一个指针初始化指向数组的第一个元素,往后一定;另一个指针指向数组的后面一个元素,往前移动。在两个指针相遇之前,第一个指针总是在第二个指针的前面,如果第一个指针指向的是偶数,就和第二个指针中指向的奇数进行互换。下面以数组{1,2,3,4,5}为例说明。

调整数组{1,2,3,4,5}使得奇数位于偶数前面的过程

图的说明:

  1. 图(a)中把第一个指针指向数组的第一个数字,第二个指针指向数组的第二个位置
  2. 向后移动第一个指针,使它指向一个偶数;向前移动第二个指针,使它指向一个奇数
  3. 交换此时两个指针指向的值。
  4. 继续前面1,2,3等操作,直到第二个指针移动到了第一个指针的前面。

基于上面的分析,写下如下Java代码。

public void ReorderOddEven(int[] array) {if (array == null || array.length == 0) {return;}int pStart = 0;int pEnd = array.length - 1;while (pEnd > pStart) {// 向后移动,直到它指向偶数while (!isEven(array[pStart])) {pStart++;}// 向前移动,直到它指向奇数while (isEven(array[pEnd])) {pEnd--;}if (pEnd > pStart) {// 交换swap(array, pStart, pEnd);}}
}public void swap(int[] array, int i, int j) {int tmp = array[i];array[i] = array[j];array[j] = tmp;
}private boolean isEven(int n) {
//         return n % 2 == 0;return (n & 0x1) == 0;
}

考虑可扩展的解法

如果是资深的开发职位,需要考虑程序的扩展性,提出能够解决这一系列问题的解法。例如,数组中按照大小分为两个部分,前面为负数后面为非负数;能被3整数和不能被3整除的数等等。就是将前面的函数解耦出两部分:一是判断数字应该在数组的前半部分还是后半部分,二是拆分数组的操作。(前面代码已经完成了这部分解耦工作)

测试用例

  1. 输入数组中奇数和偶数交替出现;所有的偶数都在奇数的前面;所有的奇数都在偶数前面
  2. 特殊输入测试:输入NULL数组;输入的数组中只有一个元素。

这篇关于调整数顺序使奇数位于偶数前面的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1104909

相关文章

顺序表之创建,判满,插入,输出

文章目录 🍊自我介绍🍊创建一个空的顺序表,为结构体在堆区分配空间🍊插入数据🍊输出数据🍊判断顺序表是否满了,满了返回值1,否则返回0🍊main函数 你的点赞评论就是对博主最大的鼓励 当然喜欢的小伙伴可以:点赞+关注+评论+收藏(一键四连)哦~ 🍊自我介绍   Hello,大家好,我是小珑也要变强(也是小珑),我是易编程·终身成长社群的一名“创始团队·嘉宾”

web群集--nginx配置文件location匹配符的优先级顺序详解及验证

文章目录 前言优先级顺序优先级顺序(详解)1. 精确匹配(Exact Match)2. 正则表达式匹配(Regex Match)3. 前缀匹配(Prefix Match) 匹配规则的综合应用验证优先级 前言 location的作用 在 NGINX 中,location 指令用于定义如何处理特定的请求 URI。由于网站往往需要不同的处理方式来适应各种请求,NGINX 提供了多种匹

[数据结构]队列之顺序队列的类模板实现

队列是一种限定存取位置的线性表,允许插入的一端叫做队尾(rear),允许删除的一端叫做队首(front)。 队列具有FIFO的性质 队列的存储表示也有两种方式:基于数组的,基于列表的。基于数组的叫做顺序队列,基于列表的叫做链式队列。 一下是基于动态数组的顺序队列的模板类的实现。 顺序队列的抽象基类如下所示:只提供了接口和显式的默认构造函数和析构函数,在派生类中调用。 #i

[数据结构]栈之顺序栈的类模板实现

栈的数组实现形式,采用动态分配数组,不够时可以调整栈的大小。 Stack.h文件:主要定义栈的抽象基类,提供公共的接口函数。 #ifndef STACK#define STACK//栈的抽象基类template<class T>class Stack{public:Stack(){}~Stack(){}virtual void Push(const T& x)=0;virt

C++中类的构造函数调用顺序

当建立一个对象时,首先调用基类的构造函数,然后调用下一个派生类的 构造函数,依次类推,直至到达派生类次数最多的派生次数最多的类的构造函数为止。 简而言之,对象是由“底层向上”开始构造的。因为,构造函数一开始构造时,总是 要调用它的基类的构造函数,然后才开始执行其构造函数体,调用直接基类构造函数时, 如果无专门说明,就调用直接基类的默认构造函数。在对象析构时,其顺序正好相反。

七、Maven继承和聚合关系、及Maven的仓库及查找顺序

1.继承   2.聚合   3.Maven的仓库及查找顺序

线性表中顺序表的合并

对两个顺序表进行合并,算法的复杂度为O(La.size+Lb.size)。 已知: 顺序线性表La和Lb的元素按值非递减排列 归并La和Lb得到的顺序线性表Lc,Lc的元素也按值非递减排列。 代码定义: void mergeList(SeqList *La,SeqList *Lb,SeqList *Lc){Lc->capacity = La->size + Lb->size;Lc->b

理解C++全局对象析构顺序与 IPC 资源管理:避免 coredump

文章目录 0. 概述1. 问题背景2. 问题分析3. 解决方案:手动释放资源4. 深入剖析:为什么手动调用 `reset()` 有效?5. 延伸思考:如何避免全局对象带来的问题?6. 总结 0. 概述 在编写 C++ 程序时,使用全局或静态对象有时可能会导致不可预期的崩溃(如 coredump)。这类崩溃通常源于对象的析构顺序、资源的管理方式,以及底层资源(如 IPC 通道或共

逆序和顺序创建单链表

单链表是一种顺序的存储方式,数据结构学的不好,考研又是必考内容,只好从头开始学习,相信不断地积累会有更好的爆发! 首先单链表的创建,单链表是建立在结构体的基础上,要创建单链表首先要建立起一个储存数据的结构体: struct node{int elem;node *next;};elem是数据域,用来存放你要输入的数据,next是指向下个存放数据节点的指针同为node 类型; 下面是

安卓实现弹出软键盘屏幕自适应调整

今天,我通过尝试诸多方法,最终实现了软键盘弹出屏幕的自适应。      其实,一开始我想通过EditText的事件来实现,后来发现,安卓自带的函数十分强大,只需几行代码,便可实现。实现如下:     在Manifest中设置activity的属性:android:windowSoftInputMode="adjustUnspecified|stateHidden|adjustResi