剑指 面试题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) } }