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

相关文章

来自专栏阮一峰的网络日志

图解 Monad

函数式编程有一个重要概念,叫做Monad。 ? 网上有很多解释(这里和这里),但都很抽象,不容易看懂。我尝试了好多次,还是不明白Monad到底是什么。 ? 昨天...

3174
来自专栏Golang语言社区

厚土Go学习笔记 | 18. 数组

数组由一组数据类型相同的值组成。 定义一个整数数组 var a [10]int 这个数组由10个整数组成的。 数组的长度是其类型的一部分,因此数组不能改变大小。...

3085
来自专栏数据结构与算法

计数排序

算法思想 编辑 计数排序对输入的数据有附加的限制条件: 1、输入的线性表的元素属于有限偏序集S; 2、设输入的线性表的长度为n,|S|=k(表示集合S中元素...

27810
来自专栏诸葛青云的专栏

C语言什么是结构体?初步学习C语言结构体三部曲

结构体部分内容,涉及结构体定义,结构体变量,结构体指针,结构体数组,更多内容敬请关注。

703
来自专栏知识分享

结构体

数据结构  最慢一星期一章   2015.10.5   一       20:33     首先  我还不知道的一些基础知识 结构体定义并不是定义一个变量,而是...

2706
来自专栏代码世界

Python之匿名函数

匿名函数 匿名函数:为了解决那些功能很简单的需求而设计的一句话函数。 #这段代码 def calc(n): return n**n print(calc...

3289
来自专栏电光石火

PHP获取时间戳的毫秒

php获取时间的方式是time(); 那么如果是涉及需要精细的时间的应用,那么怎么获取呢? /** 获取当前时间戳,精确到毫秒 */ functi...

1829
来自专栏LIN_ZONE

PHP 类型判断和NULL,空值检查

 PHP是一种宽松类型的编程语言,在函数中对传入的参数值的“类型”以及”值是否为空或者NULL“进行检查是不可缺少的步骤。

512
来自专栏前端小作坊

0.1+0.2=0.30000000000000004问题的探究

首先声明这不是bug,原因在与十进制到二进制的转换导致的精度问题!其次这几乎出现在很多的编程语言中:C/C++,Java,Javascript中,准确的说:“使...

591
来自专栏互联网大杂烩

快速排序

快速排序是找出一个元素(理论上可以随便找一个)作为基准(pivot),然后对数组进行分区操作,使基准左边元素的值都不大于基准值,基准右边的元素值 都不小于基准值...

502

扫描关注云+社区