剑指 offer代码解析——面试题35第一个只出现一次的字符

本题的详细解析均在代码注释中:

import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;

/**
 * 题目:在字符数组中找出第一个只出现一次的字符。
 * @author 大闲人柴毛毛
 * @date 2016年3月24日
 */
public class FirstChar {
	/**
	 * 分析:本题最直观的思路是从头到尾扫描数组,假设当前扫描的字符为a[i],
	 * 若尚未统计a[i]出现的次数的话,则从a[i]开始,向后统计a[i]出现的次数。
	 * 这种方式需要扫描数组n次,且每次还需要进行n次扫描统计a[i]出现的次数,因此时间复杂度为O(n^2)。
	 * 是否有更高效的方法呢?
	 */
	
	
	/**
	 * 要想降低时间复杂度,我们就应该想到“用空间换取时间”的思想。
	 * 如果我们只对数组扫描一遍,那么需要额外的空间来存储每个字符在数组中出现的个数。
	 * 这个数据结构能支持通过字符来获取该字符出现的次数。在Java中,Map能存储任意类型的键值对,因此适合本题。
	 * 代码如下:
	 */
	
	/**
	 * 获取字符数组中第一个只出现一次的字符
	 * @param a 字符数组
	 * @return 返回第一个只出现一次的字符
	 */
	private static boolean result = true;
	public static char getFirstChar(char[] a){
		
		//若数组为空
		if(a==null || a.length<=0){
			System.out.println("字符数组为空!");
			result = false;
			return ' ';
		}
		
		//创建Map,用于存储“字符”-“该字符出现的次数”
		Map<Character,Integer> map = new LinkedHashMap<Character,Integer>();
		
		//扫描数组,统计每个字符出现的次数
		for(int i=0;i<a.length;i++){
			//获取字符a[i]到目前为止出现的次数
			int count; 
			if(map.get(a[i])==null) 
				count = 0;
			else
				count = map.get(a[i]);
			
			//将次数+1存入map
			map.put(a[i], ++count);
		}
		
		//遍历map,取出第一个个数为1的字符
		Set<Character> keys = map.keySet();
		for(char key : keys){
			if(map.get(key)==1)
				return key;
		}
		
		return ' ';
	}
	
	
	
	/**
	 * 测试
	 */
	public static void main(String[] args){
		char[] a = {'a','b','a','c','c','d','e','f','b'};
		System.out.println(getFirstChar(a));
	}
}

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

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏老九学堂

弱鸡别走,指针让你更强壮!

指针可以加上或减去一个整数。指针的这种运算的意义和通常的数值的加减运算的意义是不一样的,以单元为单位。例如:

722
来自专栏北京马哥教育

练习正则表达式

正则表达式可以通过元字符(规则)来匹配查找相关的的字符集合。他与通配符是有区别的。而且相关的使用工具对正则表示的元字符的是有区别的。 首先我们先来了解下常用的元...

2729
来自专栏程序员八阿哥

年薪20万Python工程师进阶(4):一文读懂Python可迭代对象、迭代器和生成器

序列可以迭代的原因:iter 函数。解释器需要迭代对象 x 时,会自动调用 iter(x)。内置的 iter 函数有以下作用:

833
来自专栏开源优测

[快学Python3]类基础

概述 Python从设计之初就是面向对象的编程语言,所以在Python中创建一个类和对象是轻而易举的。 本文就Python的面向对象编程进行分享。 几个基本的概...

3176
来自专栏青枫的专栏

正则表达式的规则

593
来自专栏武培轩的专栏

剑指Offer-重建二叉树

题目描述 输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,...

3508
来自专栏Golang语言社区

厚土Go学习笔记 | 04. 导入和导出的不同 用math.Pi来举例

go语言代码中的import是导入包。 导入单个的包可以写成 import "fmt" 如果导入多个包的话,可以用圆括号进行组合导入,写成下面这个样子。 imp...

2666
来自专栏前端学习心得

ES6数组的扩展----Array.from()和Array.of()

如果一个对象的所有键名都是正整数或零,并且有length属性,那么这个对象就很像数组,语法上称为“类似数组的对象”(array-like object),即为伪...

663
来自专栏十月梦想

数组相关处理函数

********************************************************************************...

825
来自专栏测试开发架构之路

C和指针小结(C/C++程序设计)

C和指针 相关基础知识:内存的分配(谭浩强版) 1、整型变量的地址与浮点型/字符型变量的地址区别?(整型变量/浮点型变量的区别是什么) 2、int *p,指向整...

32711

扫码关注云+社区