首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
admin
2019-03-29
162
问题
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为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
程序员面试
相关试题推荐
AnE-mailtoaRoommate写给室友的邮件YouaregoingtostudyabroadandshareanapartmentwithJohn,alocalstudent.Writehimane-
TheSecondWorldWar,______theearlieronein1914,promptedpublicconcernaboutthephysicalandintellectualwell-beingoft
Weakdollarorno,$46,000—thepriceforasingleyearofundergraduateinstructionamidtheredbrickofHarvardYard—is【C1】__
描述一下C#中索引器的实现过程,是否只能根据数字进行索引?
求最大连续递增数字串(如“ads3sl456789DF3456ld345AA”中的“456789”)
如果字符串一的所有字符按其在字符串中的顺序出现在另外一个字符串二中,则字符串一称之为字符串二的子串。注意,并不要求子串(字符串一)的字符必须连续出现在字符串二中。请编写一个函数,输入两个字符串,求它们的最长公共子串,并打印出最长公共子串。例如:输入两个
.net中读写数据库需要用到哪些类?他们的作用
类CMyString的声明如下:classCMyString{public:CMyString(char*pData=NULL);CMyString(constCMyString&str);~CMyString(void);
利用MSN给bob@sina.com发送电子邮件内容“8号晚上到我家一起吃饭”。
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
随机试题
WindowsServer2003服务器中,( )是进行磁盘控制、目录和文件权限管理的简单工具。
Fillingincompanyapplicationformscanbecomeaboringandrepetitivetask,yetanycarelessnessonanapplicant’spartcand
下列有关眼睑基底细胞癌的说法,不正确的是
甲公司委托乙研究所开发一项技术,乙研究所指派工程师王某进行研究,并最终完成一项研究成果。因对专利申请权的归属未约定,且双方无法达成补充协议,为此引起纠纷。此项专利申请权应()。(2011年单项选择第12题)
对收集整理的资料进行分析研究,运用比较、归纳、推理或统计等方法发现各变量之间的内在联系,揭示数量特征及含义,得出社会调查结论。其属于调查与收集社会信息基本程序中的()。
S公司新研发的产品由于其自身特性,加之公司的大力宣传,广受顾客青睐。该公司所在产业的产品市场增长率很高,虽然现在的相对市场占有率不是很大,但是未来发展的空间很大。根据波士顿矩阵理论,下列关于该产品的说法中不正确的是()。
导游人员在年审中,考评等级为暂缓通过年审的()。
根据《未成年人保护法》,对孤儿、无法查明其父母或者其他监护人的以及其他生活无着的未成年人,由()收留抚养。
强调引导小组组员建立团结、互助与合作的关系体现了小组工作()的特点。
股票体现的是()。
最新回复
(
0
)