【剑指Offer】13、调整数组顺序使奇数位于偶数前面
2024-08-31 05:56:53
题目描述:
输入一个整数数组,实现一个函数来调整该数组中数字的顺序,使得所有的奇数位于数组的前半部分,所有的偶数位于数组的后半部分,并保证奇数和奇数,偶数和偶数之间的相对位置不变。
解题思路:
首先,如果不考虑奇数和奇数,偶数和偶数的相对位置,那么我们有一种双指针解法来求解,类似于快排,维护两个指针,第一个指针指向数组的第一个数字,第二个指针指向数组的最后一个数字。第一个指针向后移,第二个指针向前移,如果第一个指针指向偶数,第二个指针指向的是奇数,则交换着两个数字,接着继续移动直到两指针相遇。
上面的方法看似不错,但是对本题不适用,因为本题有相对位置不变的要求,直接交换会导致相对位置改变。因此,我们采用下面的思路来解决本题。
本题解法:对数组进行遍历,设置两个指针even和odd,even指向当前第一个偶数,odd从这个偶数之后开始查找,找到第一个奇数,此时为了相对位置不变,不能直接交换even和odd,而是将从even到odd-1的元素都依次向后移一个位置,将odd指向的那个奇数放到even的位置。然后再找下一个偶数,重复这一过程,最终就可以将奇数都放到偶数的前面,并且保证了相对位置的不变。
编程实现(Java):
public void reOrderArray(int [] array) {
int len=array.length;
int even=0,odd=0; //当前序列的第一个奇数和第一个偶数
while(odd<len && even<len){
while(even<len && array[even]%2!=0) //找到第一个偶数even
even++;
odd=even+1;
//找偶数之后的第一个奇数
while(odd<len && array[odd]%2==0)
odd++;
if(odd>=len) //注意判断,防止溢出
break;
//把奇数取出来,从even到odd-1的元素都向后移
int temp=array[odd];
for(int i=odd;i>even;i--)
array[i]=array[i-1];
array[even]=temp; //奇数放在原来even的位置
even++;
}
}
最新文章
- 基于.NET平台常用的框架整理(转)
- mysql数据表分表策略(转)
- mysql随机获取一条或者多条数据
- 利用c#反射实现实体类生成以及数据获取与赋值
- Bsie(鄙视IE)
- 【转】Java 集合系列03之 ArrayList详细介绍(源码解析)和使用示例
- 用R语言 做回归分析
- Android动态换肤(二、apk免安装插件方式)
- BZOJ_1827_[Usaco2010 Mar]gather 奶牛大集会_树形DP
- centos7 无界面静默安装 oracle
- 一、VS2017 的创建程序
- 本人AI知识体系导航 - AI menu
- C#简单的九九乘法表
- Java集合之Hashtable源码分析
- MAVEN 创建项目
- linux rz sz
- js的let语句在安卓手机端的QQ浏览器出错的问题
- Chrome DevTools快捷键
- NO.013-2018.02.18《鹊桥仙&#183;纤云弄巧》宋代:秦观
- sqlserver操作各种文件方法
热门文章
- hive 报错/tmp/hive on HDFS should be writable. Current permissions are: rwx--x--x
- Ubuntu下调整时区时间
- 猫猫学iOS之UILabel设置圆角不成功所做调控更改
- UNIX环境编程学习——反思认识
- poj 1837 Balance (0 1 背包)
- nyoj 1238 最少换乘 (河南省第八届acm程序设计大赛)
- test框架搭建
- oc46--nonatomic, retain
- Coursera Algorithms week1 查并集 练习测验:3 Successor with delete
- fopen文件目录问题