首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
admin
2019-03-29
159
问题
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为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
程序员面试
相关试题推荐
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
TheMagicofSoundMusicisoneofthemostbeautifulformsofartisticexpressionseverinvented.Inmoviesandplays,musi
Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressyourownopinion.
Directions:Inthissection,youareaskedtowriteanessaybasedonthefollowinginformation.Makecommentsandexpressy
删除字符串中的数字并压缩字符串(神州数码以前笔试题),如字符串”abc123de4fg56”处理后变为”abcdefg”。注意空间和效率。(下面的算法只需要一次遍历,不需要开辟新空间,时间复杂度为O(N))
在控制面板中,将鼠标的"右手习惯"改为"左手习惯"。
在foxpro中定义数据库结构时,字段名的宽度最多可以是()。A.2B.4C.10D.16
下列有关break和continue语句的叙述中,正确的是________。
路由器的主要作用是()。
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
随机试题
脐带无菌结扎后逐渐干燥,一般脱落的时间为()
根据知觉对象的特征可以把知觉分为()、()、()
A.脊神经节B.脊髓胶状质C.脊髓后角固有核D.脊髓I、Ⅳ和V层E.胸核躯干四肢的浅感觉传导通路的第二级神经元胞体位于()
A.热因热用B.寒因寒用C.寒者热之D.热者寒之适用于阳盛格阴的真热假寒证治法
下列哪项不是慢性贫血患者的特点
桂枝汤原方服法要求“服已须臾,啜热稀粥一升余”,其意义在于
我国西北地区主要的地理特征是()。
如图,三个图形的周长相等,则a:b:c是多少?()
某工厂生产某产品,1月份每件产品的销售利润是出厂价的25%,2月份每件产品的出厂价降低了10%,成本不变,销售件数比1月份增加80%,则销售利润比1月份的销售利润增长()。
A、cametoshootatthetargetB、cametohavealookatthegardenC、cametoseehimC一天,朋友来拜访他。
最新回复
(
0
)