首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
admin
2019-03-29
127
问题
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为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
程序员面试
相关试题推荐
TheUnitedStatesInterstateHighwaySystemisaninfrastructurefeatofunprecedentedproportions.Notonlydoesitjoinallfi
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
TheMagicofSoundMusicisoneofthemostbeautifulformsofartisticexpressionseverinvented.Inmoviesandplays,musi
输入一个整数数组,判断该数组是不是某二元查找树的后序遍历的结果。如果是返回true,否则返回false。例如输入5、7、6、9、11、10、8,由于这一整数序列是如下树的后序遍历结果:8/\610
大概描述一下ASP。NET页面的生命周期
两个单向链表,找出它们的第一个公共结点。链表的结点定义为:structListNode{intm_nKey;ListNode*m_pNext;};
触发器分为事前触发和事后触发,这两种触发有和区别。语句级触发和行级触发有何区别。
游标的作用?如何知道游标已经到了最后?
在Excel中,公式SUM(C2:C6)的作用是()。A.求C2到C6这五个单元格数据之和B.求C2和C6这两个单元格数据之和C.求C2和C6两单元格的比值D.以上说法都不对
随着网络信息技术的进步和社会信息化程度的不断提高,一个由庞大的网络产业带动,并导致整个经济社会产生巨大变革的数字经济时代已经离我们越来越近。目前,“数字化校园”、“数字企业”、“数字城市”等一系列项目快速上马,在这些项目中,信息的数字化与数字信息的网络传输
随机试题
1904年,孙中山发表的指出只有推翻清政府的统治,建立“中华民国”,才能真正解决中国问题的文章是________。
银翘散与桑菊饮功用的主要区别是()
A.比色法B.比浊法C.在490nm处测定吸收度的方法D.高效液相色谱法E.薄层色谱法
某高层建筑采用梁板式筏形基础,柱网尺寸为8.7m×8.7m,柱横截面为1450mm×1450mm,柱下为交叉基础梁,梁宽为450mm,荷载效应基本组合下地基净反力为400kPa,设梁板式筏基的底板厚度为1000mm,双排钢筋,钢筋合力点至板截面近边的距离取
某平原水库水体面积为4500hm2,水深8.Om。在进行渔业资源调查时,采取的样品数至少应为()。
投资者购买保证收益理财计划时不承担任何风险。()
生产、销售不符合卫生标准的化妆品,实际销售金额5万元以上,但未造成严重后果的,应定( )。
甲不慎落水,乙奋勇抢救,抢救过程中致甲面部受伤,同时乙丢失手机一部。下列表述中哪一说法是正确的?
华盛顿国立气象研究所的墙上有这么一句话:“当我们做对了,没有人会记得;当我们做错了,没有人会忘记。”气象研究所的墙上写这句话的目的是()。
A、 B、 C、 A注意听对方的意见。(A)Ithinkso.是对所问之事表示同意时的回答,故为正确答案。(B)重复使用trip一词,易造成误导,并且,此项的时态和内容均与问题无关。(C)针对是否有足够的差旅费的提问
最新回复
(
0
)