剑指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 条评论
登录 后参与评论

相关文章

来自专栏xiaoxi666的专栏

状态机编程思想(1):括号内外字符串统计

我们拿到这个问题时,第一感觉往往是顺序遍历字符串,并检测左右相邻字符是否满足边界条件,从而进行分支处理。但是这样做有以下棘手之处:

693
来自专栏皮振伟的专栏

[linux][network]互联网后台模型

前言: 虽然话题的范围有点大,但是在这里作者不打算谈框架,侃架构。 这里也只是作者最熟悉的一种后台架构模型。 并发模型: 多进程模型: 来一个请求,设定环境...

2638
来自专栏Golang语言社区

Go语言的fmt包中文教程

Fmt包 import "fmt" 简介 ▾ Package fmt包含有格式化I/O函数,类似于C语言的printf和scanf。格式字符串的规则来源于C但更...

3427
来自专栏C/C++基础

打印1到最大的n位数

这道题是面试过可能会遇到的手写代码题。如n为3时,那么需要打印1到999。需要注意的是当输入的n很大时,最大的n位数是不能通过int或者long long in...

551
来自专栏青玉伏案

ReactiveSwift源码解析(六) SignalProtocol的take(first)与collect()延展实现

上篇博客我们聊了observe()、map()、filter()延展函数的具体实现方式以及使用方式。我们在之前的博客中已经聊过,Signal的主要功能是位于Si...

1798
来自专栏智能合约

Phalcon入门教程之模型CURD(2)

1092
来自专栏mathor

位与进制

 这里我假设读者有二进制的思维,知道(3)~10~=(011)~2~将十进制转换为二进制的方法

371
来自专栏Golang语言社区

Golang模板语法简明教程

【模板标签】 模板标签用"{{"和"}}"括起来 【注释】 {{/* a comment */}} 使用“{{/*”和“*/}}”来包含注释内容 【变量】 {{...

32812
来自专栏web前端教室

不学不知道,sort()方法中的坑

今天的前端零基础课,在讲到js中的sort()排序方法的时候,说sort()这个方法在给数字排序的时候,根本不是按数字大小来排序的。 它是把数字都当成字符串来看...

17010
来自专栏linux驱动个人学习

Android图形显示之硬件抽象层Gralloc【转】

1605

扫码关注云+社区