首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
计算机
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为O(n)。
admin
2019-03-29
71
问题
输入一个整数数组,调整数组中数字的顺序,使得所有奇数位于数组的前半部分,所有偶数位于数组的后半部分。要求时间复杂度为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
程序员面试
相关试题推荐
AWelcomeE-mail欢迎邮件Someinternationalstudentsarecomingtoyouruniversity.Writethemane-mailinthenameoftheStudent
活动目录的作用
输入一个链表的头结点,从尾到头反过来输出每个结点的值。链表结点定义如下:structListNode{intm_nKey;ListNode*m_pNext;};
n个数字(0,1,…,n-1)形成一个圆圈,从数字0开始,每次从这个圆圈中删除第m个数字(第一个为当前数字本身,第二个为当前数字的下一个数字)。当一个数字删除后,从被删除数字的下一个继续删除第m个数字。求出在这个圆圈中剩下的最后一个数字。
数据库的优化设计?
为邮件到达后应用规则“若发件人包含‘mary@sina.com’转发到wangtao@sina.com”。
在Excel中,函数ABS(ROUND(-1.478,2))的计算结果是()。A.-1.478B.1.48C.-1.48D.1.5
Powerpoint2000中,使用()菜单中的“幻灯片母版”命令,进入幻灯片母版设计窗口,更改幻灯片的母版。A.编辑B.工具C.视图D.格式
计算机能直接识别和执行的语言是()A.机器语言B.高级语言C.数据库语言D.汇编程序
在数据库系统中,“事务”是访问数据库并可能更新各种数据项的一个程序执行单元。为了保证数据完整性,要求数据库系统维护事务的原子性、一致性、隔离性和持久性。针对事务的这4种特性,考虑以下的架构设计场景:假设在某一个时刻只有一个活动的事务,为了保证事务
随机试题
精子低渗肿胀试验的参考值为
首选用于治疗脓肿溃破后有袋脓现象,经其他引流、垫棉等法治疗无效的外科手术疗法是
甲与乙共同出资购买别墅一套,后出租给某公司使用。在租赁期间,乙因缺钱花,欲出让自己的共有份额。承租的公司表示愿意购买,则此房屋属于乙的份额应卖给()。
关于减刑,下列说法正确的是:()
下列哪一选项所列举的证据属于补强证据?
与计算“营业利润”无关的因素是()。
申请期货公司董事长、监事会主席、独立董事的任职资格,应当由本人向中国证监会或者其授权的派出机构提出申请。()
下列关于自然人民事行为能力的表述中,错误的是()。
对1个单位质量的含污物体进行清洗,清洗前其清洁度(含污物体的清洁度定义为:1-为0.8,要求洗完后的清洁度为0.99,有两种方案可供选择,方案甲:-次清洗;方案乙:两次清洗,该物体初次清洗后受残留水等因素影响,其质量变为a(1≤a≤3),设用z单位质量的水
某月,吴局长因公连续出差了7天,将这7天的日期加起来,结果刚好为77。则吴局长出差的最后一天是当月的()。
最新回复
(
0
)