剑指offer代码解析——面试题14调整数组顺序使奇数在偶数之前

本题详细解析都已在代码中注释了:

/**
 * 题目:输入一个数组,要求将奇数放在数组的前半段,偶数放在数组的后半段 
 * @author 大闲人柴毛毛
 */
public class Reorder {
	/**
	 * 分析:本题只要求前半段为奇数,后半段为偶数,没有要求有序,
	 * 因此可以采用快速排序中一趟排序的思想:
	 * 使用两个指针i、j,i指向头、j指向尾,分别向后、向前扫描;
	 * 若i遇到偶数则停下,j遇到奇数则停下,交换这两个数,
	 * 然后继续重复上述操作,直到i、j相遇为止。代码如下:
	 * PS:快速排序算法请看我的博客《剑指 offer——快速排序》
	 */
	public static boolean reorder(int[] a){
		//若数组为空
		if(a==null || a.length==0){
			System.out.println("数组为空!");
			return false;
		}
		
		//若数组只有一个元素,那不做任何操作
		if(a.length==1){
			System.out.println("数组长度为1,无需排序!");
			return true;
		}
		
		//若数组长度超过2,则进行排序
		int i=0,j=a.length-1;
		while(i<j){
			//i从头向后扫描,若当前元素为奇数,则继续往后扫描,若为偶数,i停止扫描。
			while(a[i]%2==1)
				i++;
			//j从后向前扫描,若当前元素为偶数,则继续往前扫描,若为奇数,j停止扫描。
			while(a[j]%2==0)
				j--;
			//当i、j都停止时,如果i和j还没有相遇,就交换这两个数
			if(i<j){
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		return true;
	}
	
	
	/**
	 * 上述代码运行过后会出现死循环!
	 * 当数组全为奇数时,i无限向后寻找,因此出现死循环。
	 * 因此,在i向后、j向前的循环中应多加一个判断:若i搜索到末尾,则停止、若j搜索到开头,则停止。
	 * 修改后的代码如下:
	 */
	public static boolean reorder_modify(int[] a){
		//若数组为空
		if(a==null || a.length==0){
			System.out.println("数组为空!");
			return false;
		}
		
		//若数组只有一个元素,那不做任何操作
		if(a.length==1){
			System.out.println("数组长度为1,无需排序!");
			return true;
		}
		
		//若数组长度超过2,则进行排序
		int i=0,j=a.length-1;
		while(i<j){
			//i从头向后扫描,若当前元素为奇数,则继续往后扫描,若为偶数,i停止扫描。
			while(i<a.length-1 && a[i]%2==1)
				i++;
			//j从后向前扫描,若当前元素为偶数,则继续往前扫描,若为奇数,j停止扫描。
			while(j>0 && a[j]%2==0)
				j--;
			//当i、j都停止时,如果i和j还没有相遇,就交换这两个数
			if(i<j){
				int temp = a[i];
				a[i] = a[j];
				a[j] = temp;
			}
		}
		return true;
	}
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏ChaMd5安全团队

PHP源码分析之parse_url()的2个小trick

之前从phithon师傅的代码审计小密圈看到pupiles师傅发过一篇文章,讲了parse_url()的很多小tricks,可惜只是给出了tricks的利用方法...

1213
来自专栏软件开发 -- 分享 互助 成长

C++ STL 中erase()的使用需要小心

C++ STL极大的方便了用户编写程序,但是同时一不小心也会犯一些错误,如erase()造成迭代器失效经常会引起错误。 错误示例: std::lis...

19510
来自专栏V站

PHP常用函数总结

$x = 5.7; $y = 1.3; // 两个浮点数,x>y 浮点余数 $r = fmod($x, $y); // $r equals 0.5, becau...

2632
来自专栏小白的技术客栈

Python基础语法-内置数据结构概览

本文内容非常简单,主要介绍接下来要讲的内容。那就是Python的内置数据结构。今天只是简单介绍一下Python都有哪些内置数据结构,这样就可以循序渐进地进行学习...

3367
来自专栏ml

C++知识整理(在此感谢大牛的整理)

这篇文章主要讲解如何在C++中使用cin/cout进行高级的格式化输出操作,包括数字的各种计数法(精度)输出,左或右对齐,大小写等等。通过本文,您可以完全脱离s...

2514
来自专栏Script Boy (CN-SIMO)

几个整数求和

任务描述 在eclipse中通过配置运行参数,编写程序求这些整数参数之和然后输出参数个数与所求之和。 设计思想 获取的参数是String类型的,通过Intege...

1990
来自专栏专注数据中心高性能网络技术研发

[Effective Modern C++(11&14)]Chapter 4: Smart Pointers

2452
来自专栏我是攻城师

JDK8中HashMap的工作原理剖析

44511
来自专栏Hongten

python开发_函数的参数传递

在这个用例中,我们要讨论的是关于函数的传参问题 我所使用的python版本为3.3.2

814
来自专栏决胜机器学习

PHP数据结构(二十五) ——并归排序

PHP数据结构(二十五)——并归排序 (原创内容,转载请注明来源,谢谢) 一、概述 并归排序是将两个或两个以上的有序表组合成一个新的有序表。采用并归的思想进...

3608

扫码关注云+社区