福州网站建设liedns,谷歌浏览器下载app,网站 谁建设谁负责,在线教育网站开发软件LintCode 373: Partition Array 题目描述 分割一个整数数组#xff0c;使得奇数在前偶数在后。 样例 给定[1, 2, 3, 4]#xff0c;返回[1, 3, 2, 4]。 Thu Feb 23 2017 思路 简单题#xff0c;可以很自然地想到再用一个答案数组#xff0c;从头到尾遍历一遍#xff0c;遇到… LintCode 373: Partition Array 题目描述 分割一个整数数组使得奇数在前偶数在后。 样例 给定[1, 2, 3, 4]返回[1, 3, 2, 4]。 Thu Feb 23 2017 思路 简单题可以很自然地想到再用一个答案数组从头到尾遍历一遍遇到奇数就放到答案数组的前面遇到偶数就放到答案数组的后面。 还有另一种方法跟快速排序的形式有点像即从前面找到一个偶数同时从后面找到一个奇数将两个数调换。 虽然两种方法的时间复杂度都是\(O(n)\)但是第二种方法的空间复杂度是\(O(1)\)算是更优的方法。 代码 // 奇偶分割数组
void partitionArray(vectorint nums)
{if (nums.size() 0) return;vectorint::iterator l nums.begin(), r nums.end() - 1;while(l ! r){while (l ! r *l % 2 1) l;while (l ! r *r % 2 0) --r;swap(*l, *r);}
} 转载于:https://www.cnblogs.com/genkun/p/6436058.html
