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

相关文章

来自专栏吾爱乐享

java之学习vector类的特有功能

1222
来自专栏流媒体

C语言数组

913
来自专栏Python小屋

1000道Python题库系列分享二(48道)

本系列题目共约1000道,下一期题库分享时发布本期题目参考答案,可以在微信公众号菜单查看系列题目。 上一期题目链接1000道Python题库系列分享一(17道)...

5448
来自专栏Redis

Redis类型之lists类型

9、rpoplpush 从第一个list的尾部移除元素并添加到第二个list的头部,最后返回被移除的元素值,整个操作是原子的,如果第一个list是空或者不存在...

1400
来自专栏cs

xml基本知识点

xml, Extensible Markup Language,可扩展的标记语言。 ? xml文档结构.jpg xml文档的规则 1.0 xml文档必须以一个...

3325
来自专栏Kevin-ZhangCG

[ Java学习基础 ] Java构造函数

2106
来自专栏小樱的经验随笔

strncmp函数——比较特定长度的字符串

strncmp函数用于比较特定长度的字符串。 头文件:string.h。 语法  int strncmp(const char *string1, const ...

2939
来自专栏北京马哥教育

还不会Python正则表达式?看这篇文章试试

今天写爬虫偶然想到了初学正则表达式时候,看过一篇文章非常不错。检索一下还真的找到了。 re模块 re.search 经常用match = re.search(p...

3286
来自专栏Vamei实验室

Python基础03 序列

sequence 序列 sequence(序列)是一组有顺序的元素的集合 (严格的说,是对象的集合,但鉴于我们还没有引入“对象”概念,暂时说元素) 序列可以包含...

1865
来自专栏向治洪

hashCode与equals的区别

hashCode与equals HashSet和HashMap一直都是JDK中最常用的两个类,HashSet要求不能存储相同的对象,HashMap要求不能存储相...

16710

扫码关注云+社区