调整数组顺序使奇数位于偶数前面,且奇数之间、偶数之间的相对位置不变
发布日期:2021-06-30 19:56:18
浏览次数:2
分类:技术文章
本文共 994 字,大约阅读时间需要 3 分钟。
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
题目地址:
思路:如果没有要求奇数之间、偶数之间的相对位置的话,可以直接用2个指针变量,左边往右扫到偶数就暂停,右边往左扫到奇数就暂停然后交换,依次往返,结束条件为两个指针变量的相遇。
但是这里有了这个要求,不能这样做了,考虑用空间换时间,如果遇到奇数就用一个数组存起来,遇到偶数再用另一个数组存起来就需要2个额外的数组,再最后合并到一个数组里,这是一个思路(或者2个队列也是同样的思路),现在这里优化一下,只申请一个额外的数组,将原来的数组从左往右扫,遇到奇数就存到新数组的左边,同时将原来的数组从右往左扫,遇到偶数就存到新数组的右边,这样就可以保证左边是奇数,右边是偶数,且奇数之间、偶数之间相对位置不变,再合并到原数组就ok了。
AC代码:
public class Solution { public void reOrderArray(int [] array) { int len = array.length; int[] arr = new int[len]; int start = 0; int end = len - 1; for (int i = 0; i < len; ++i) { if ((array[i] & 1) == 1) { arr[start++] = array[i]; } if ((array[len - 1 - i] & 1) == 0) { arr[end--] = array[len - 1 - i]; } } for (int i = 0; i < len; ++i) { array[i] = arr[i]; } }}
=====================Talk is cheap, show me the code=====================
转载地址:https://liuchenyang0515.blog.csdn.net/article/details/84877252 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
很好
[***.229.124.182]2024年04月19日 17时57分41秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
POJ - 2481 Cows (树状数组 入门题)
2019-04-30
CodeForces - 987C Three displays (暴力/dp)
2019-04-30
计蒜客 NAIPC 2016 F. Mountain Scenes(dp)
2019-04-30
牛客国庆集训派对Day4——I 连通块计数(思维)
2019-04-30
牛客国庆集训派对Day4——G 区间权值(找规律,双重前缀和)
2019-04-30
牛客国庆集训派对Day5——L 数论之神(找规律/数论)
2019-04-30
CodeForces - 629B Far Relative’s Problem(模拟)
2019-04-30
CodeForces - 1059B Forgery (思维)
2019-04-30
CodeForces - 456C Boredom (dp)
2019-04-30
CodeForces - 960B Minimize the error (思维,贪心)
2019-04-30
CodeForces - 97B Superset (思维/分治/构造)
2019-04-30
CodeForces - 675A Infinite Sequence(简单数论 细节)
2019-04-30
CodeForces - 1042B Vitamins (思维)
2019-04-30
ACM 2013 长沙区域赛 Collision (几何)
2019-04-30
ACM 2014 鞍山区域赛 E - Hatsune Miku (dp)
2019-04-30
反向传播&梯度下降 的直观理解程序(numpy)
2019-04-30