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

相关文章

来自专栏python3

python3--函数进阶

TypeError: func() missing 4 required keyword-only arguments: 'a', 'b', 'c', and ...

10610
来自专栏desperate633

LintCode 两个字符串是变位词题目分析代码

写出一个函数 anagram(s, t) 判断两个字符串是否可以通过改变字母的顺序变成一样的字符串。

10720
来自专栏JAVA技术站

shell学习二数组 原

类似与C语言,数组元素的下标由0开始编号。获取数组中的元素要利用下标,下标可以是整数或算术表达式,其值应大于或等于0。

5410
来自专栏WebDeveloper

python,详说正则表达式(对常用的关键字符的讲解)

[...]如果匹配的是个范围,可以这个写[0-9a-zA-B]表示0到9并a到z并A到B

13420
来自专栏Python小屋

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

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

87880
来自专栏北京马哥教育

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

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

34360
来自专栏Redis

Redis类型之lists类型

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

15800
来自专栏破晓之歌

JAVA入门1 原

下载地址:http://www.oracle.com/technetwork/java/javase/downloads/jdk9-downloads-3848...

16020
来自专栏Kevin-ZhangCG

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

27360
来自专栏Vamei实验室

Python基础03 序列

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

20550

扫码关注云+社区

领取腾讯云代金券