首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
admin
2019-03-29
145
问题
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
选项
答案
void Reorder(int *pData, unsigned int length, bool (*func)(int)); bool isEven(int n); ///////////////////////////////////////////////////////////////////////// // Devide an array of integers into two parts, odd in the first part, // and even in the second part // Input: pData - an array of integers // length - the length of array ///////////////////////////////////////////////////////////////////////// void ReorderOddEven(int *pData, unsigned int length) { if(pData == NULL || length == 0) return; Reorder(pData, length, isEven); } ///////////////////////////////////////////////////////////////////////// // Devide an array of integers into two parts, the intergers which // satisfy func in the first part, otherwise in the second part // Input: pData - an array of integers // length - the length of array // func - a function ///////////////////////////////////////////////////////////////////////// void Reorder(int *pData, unsigned int length, bool (*func)(int)) { if(pData == NULL || length == 0) return; int *pBegin = pData; int *pEnd = pData + length - 1; while(pBegin < pEnd) { // if *pBegin does not satisfy func, move forward if(!func(*pBegin)) { pBegin ++; continue; } // if *pEnd does not satisfy func, move backward if(func(*pEnd)) { pEnd --; continue; } // if *pBegin satisfy func while *pEnd does not, // swap these integers int temp = *pBegin; *pBegin = *pEnd; *pEnd = temp; } } ///////////////////////////////////////////////////////////////////////// // Determine whether an integer is even or not // Input: an integer // otherwise return false ///////////////////////////////////////////////////////////////////////// bool isEven(int n) { return (n & 1) == 0; }
解析
如果不考虑时间复杂度,最简单的思路应该是从头扫描这个数组,每碰到一个偶数时,拿出这个数字,并把位于这个数字后面的所有数字往前挪动一位。挪完之后在数组的末尾有一个空位,这时把该偶数放入这个空位。由于碰到一个偶数,需要移动O(n)个数字,因此总的时间复杂度是O(n
2
)。
要求的是把奇数放在数组的前半部分,偶数放在数组的后半部分,因此所有的奇数应该位于偶数的前面。也就是说我们在扫描这个数组的时候,如果发现有偶数出现在奇数的前面,我们可以交换他们的顺序,交换之后就符合要求了。
因此我们可以维护两个指针,第一个指针初始化为数组的第一个数字,它只向后移动;第二个指针初始化为数组的最后一个数字,它只向前移动。在两个指针相遇之前,第一个指针总是位于第二个指针的前面。如果第一个指针指向的数字是偶数而第二个指针指向的数字是奇数,我们就交换这两个数字。
转载请注明原文地址:https://kaotiyun.com/show/MRmZ777K
0
程序员面试
相关试题推荐
ThepublicationofPM2.5datahasbecomeanationalhottopic.Theenvironmentinstituteplanstoholdarelevantlecture.AsC
Publicationbiasinacademicjournalsisnothingnew.Afindingofnocorrelationbetweensportingeventsandeitherviolentcri
YouhavereceivedaletterfromSophia.Sheexpressedheradmirationformicro-bloggingandwonderedwhetheritcanreplacebook
Writeanessaybasedonthefollowingoutline.Youshouldwriteabout150wordsontheANSWERSHEET.1.教师用课外时间给学生补课赚钱的现象
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:因此返回true。如果输入7、4、6、5,没有哪棵树的后序遍历
.asp.net如何实现MVC模式,举例说明!
活动目录的作用
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
企业战略数据模型可分为两种类型:(35)描述日常事务处理中的数据及其关系;(36)描述企业管理决策者所需信息及其关系。35
随机试题
滑动轴承的内孔刮研是以主轴轴颈为最终依据的。()
患儿,男,5岁,面部及脸浮肿2天,尿少入院,2周前患脓疱病,T37.5℃。脉搏80次/min,呼吸24次/min,心肺(-),尿常规:管型(-),应考虑为()
Everyoneneedsabreak,andvacationsarenotmeantforseriousstudy.【D1】________TheSpringFestivaliscomingupsothis
女性,50岁,3个月前被自行车把撞伤上腹部,近3周来上腹隆起,进食后上腹胀满伴恶心、呕吐,查体:上腹部扪及18cm×13cm囊性肿块,钡餐透视见横结肠下移。最可能的诊断是
男性,45岁。诉左下颌后牙出现不适6个月求治。口腔检查:残冠,叩诊(±),松动(-),已做过牙髓治疗,牙龈稍红,无法再修复,拟拔除。口内其他牙未见明显异常。X线片示:远中根尖有阴影,距离下颌神经管较近
一外国旅游团想延长在某地的旅游时间,地陪应采取哪些处理措施?
甲、乙两地铁路线长1880千米,从甲地到乙地开出一辆动车,每小时行驶160千米,3小时后,从乙地到甲地开出一辆高铁,经4小时后与动车相遇,则高铁每小时行驶:
口腔癌预防的含义包括()。
下列是一组关于实践观的材料材料1“正如在社会中,每个人的能力总是最容易在动荡的情况下而不是在其他情况下发挥出来,所以同样隐蔽在自然中的事情,只是在技术的挑衅下,而不是在任其自行游荡下,才会暴露出来。”重要的方法:对自然的观察、思考和实验。
この記事の内容は信用できない。記事
最新回复
(
0
)