第一个只出现一次的字符（Java)

题目：

在字符串中找出第一个只出现一次的字符。如输入"abaccdeff"，则输出'b'。

第一思路：借助于数组来做。

开辟一个长度为26的数组，用来存放字符串中每个字符出现的次数。这样第一次扫描去统计这个字符串中字符出现的次数，第二次去统计第一个出现结果为1的次数，并输出对应的字符。

public class Main {
    //输出0代表没有满足条件的
	public static char findFirstNoRepeatChar(String str){
		if(str == null || str.trim().length()==0){
			return '0';
		}
		int []counts = new int[26];
		str = str.toLowerCase(); //防止出现大小写混乱的情况
		int len = str.length();
		for(int i = 0; i < len; i++){
			counts[str.charAt(i) - 'a']++;
		}
		for(int i = 0; i < len; i++){
			if(counts[str.charAt(i) - 'a'] == 1){
				return str.charAt(i);
			}
		}
		return '0';
	}
	
	public static void main(String[] args) {
		System.out.println(findFirstNoRepeatChar("abaccdeff"));
	}
}

小结：上面开辟的一个数组，其实就是为了让a~z对应。故演化出来的第二种做法就是利用带有<k，v>键值对的形式来解决问题。

第二思路：借助于HashMap来做。

借助于HashMap天然的集合优势，<k，v>键值对的形式，k存储字符，v存储出现的次数。故借此来找到第一个只出现一次的字符。

代码实现：

public class Main1 {

	public static char findFirstNoRepeatChar(String str){
		if(str == null || str.trim().length()==0){
			return '0';
		}
		Map<Character, Integer> map = new HashMap<Character, Integer>();
		str = str.toLowerCase(); //防止出现大小写混乱
		int len = str.length();
		int count = 0;
		for(int i = 0; i < len; i++){
			if(map.containsKey(str.charAt(i))){
				count = map.get(str.charAt(i));
				map.put(str.charAt(i), ++count);
			}else{
				map.put(str.charAt(i), 1);
			}
		}
		for(int i = 0; i < len; i++){
			if(map.get(str.charAt(i)) == 1){
				return str.charAt(i);
			}
		}
		return '0';
	}
	
	public static void main(String[] args) {
		char c1 = findFirstNoRepeatChar("abaccdeff");
		System.out.println(c1);
	}
}

小结：条条大路通罗马

相关题目一：

定义一个函数，输入两个字符串，从第一个字符串中删除在第二个字符串中出现过的所有字符。例如从第一个字符串“We are students.”中删除在第二个字符串"aeiou"中出现过的字符串得到的结果是"W r Stdnts."。

思路：

我们可以创建一个用数组实现的简单哈希表来存储第二个字符串。这样我们从头到尾扫描第一个字符串的每一个字符时，用O(1)时间就能判断出该字符是不是在第二个字符中。如果第一个字符串的长度是n，那么总的时间复杂度是O(n)。

相关题目二：

定义一个函数，删除字符串中所有重复出现的字符。例如输入"google"，删除重复的字符串之后的结果是"gole"。

思路：

我们可以创建一个用布尔型数组实现的简单的哈希表。数组中的元素的意义是其下表看作ASCII码对应的字母在字符串中是否已经出现。我们先把数组中所有的元素都设为false。以google为例，当扫描到第一个g时，g的ASCII码是103，那么我们把数组下标为103的元素设为true，就知道g在前面已经出现了。即我们用O(1)时间就能判断出每个字符是否在前面已经出现过。如果是字符串的长度是n，那么总的时间复杂度是O(n)。

相关题目三：

在英语中，如果两个单词中出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词（Anagram）。例如silent与listen、evil与live等互为变位词。完成一个函数，判断输入的两个字符串是不是互为变位词。

思路：

我们可以创建一个用数组实现的简单哈希表，用来统计字符串中每个字符出现的次数。当扫描到第一个字符串中的每个字符时，为哈希表对应的项的值增加1。接下来扫面第二个字符串，扫描到每个字符串时，为哈西边对应的项的值减去1。如果扫描完第二个字符串后，哈希表所有的值都是0，那么这两个字符串就互为变位词。