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

相关文章

来自专栏Pulsar-V

Save Camera Document

#pragma once #include "HCCamera.h" #include <time.h> #include <cstdio> #incl...

2818
来自专栏Ryan Miao

ehcache报错

jfinal2.0+tomcat7+ehcache2.6.11+Linux Linux version 2.6.18-164.el5 (mockbuild@x8...

3719
来自专栏MelonTeam专栏

Bitmap 源码阅读笔记

导语: Android 系统上的图片的处理,跟Bitmap 这个类脱不了关系,我们有必要去深入阅读里面的源码,以便在工作中能更好的处理Bitmap相关的问题...

2458
来自专栏增长技术

App Guide相关

##TourGuide https://github.com/worker8/TourGuide

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

高通msm8909耳机调试

1、DTS相应修改: DTS相关代码:kernel/arch/arm/boot/dts/qcom/msm8909-qrd-skuc.dtsi: 1 s...

7345
来自专栏前端儿

Web 前端颜色值--字体--使用,整理整理

颜色值 CSS 颜色使用组合了红绿蓝颜色值 (RGB) 的十六进制 (hex) 表示法进行定义。对光源进行设置的最低值可以是 0(十六进制 00)。最高值是 2...

2152
来自专栏Hadoop数据仓库

Oracle sqlldr 如何导入一个日期列

1. LOAD DATA INFILE * INTO TABLE test FIELDS TERMINATED BY X'9' TRAILING NULLCO...

1786
来自专栏跟着阿笨一起玩NET

c# 使用timer定时器操作,上次定时到了以后,下次还未执行完怎么处理

------解决方案-------------------------------------------------------- 开始的时候,禁用定时器,你...

2571
来自专栏专知

2018年SCI期刊最新影响因子排行,最高244,人工智能TPAMI9.455

2018年6月26日,最新的SCI影响因子正式发布,涵盖1万2千篇期刊。CA-Cancer J Clin 依然拔得头筹,其影响因子今年再创新高,达244.585...

1272
来自专栏一个会写诗的程序员的博客

java.base.jmod

/Library/Java/JavaVirtualMachines/jdk-9.jdk/Contents/Home/jmods$ jmod list java....

1112

扫码关注云+社区