剑指 面试题50：字符串中第一个只出现一次的字符。在字符串中找出第一个只出现一次的字符，如：输入“abaccdeff”，泽输出“b” 解题思路：用数组来实现哈希表；创建一个int[]数组，让int[]下标作为key（表示这个字符的ASCII码）， 下标所指向的元素作为value（表示这个字符出现的次数）；由于char是一个长度为8的字符类型，那么就有2的8次方也就是256种可能， 所以创建的int[]长度为256。 然后第一次遍历字符串将每个字符和它的出现次数填入map表；第二次遍历map表找出第一个只出现一次的字符
import java.util.Scanner; public class demo03 { public static void main(String[] args){ Scanner input = new Scanner(System.in); String str = input.next(); int[] hashMap = new int[256]; char[] ch = str.toCharArray(); // 第一次遍历字符串，生成map表，时间复杂度为O(n) for (int i = 0; i < ch.length; i++) { hashMap[ch[i]]++; } // 第二次遍历字符串，找出第一个只出现一次的字符，时间复杂度是O(1) for (int i = 0; i < ch.length; i++) { if (hashMap[ch[i]]==1){ System.out.print(ch[i]); break; } } // 所以整个函数总时间复杂度为O(n),用到一个256的辅助数组，大小为1KB，是个常数，可以认为空间复杂度为O(1) } }