LeetCode：387. 字符串中的第一个唯一字符

简介题目链接https://leetcode.cn/problems/first-unique-character-in-a-string/description/解决方式字符串 哈希表这是作者学习众多大神的思路进行解题的步骤很推荐大家解题的时候去看看题解里面大佬们的思路、想法暴力枚举思路暴力枚举字符串中的所有元素判断是否有相同的元素这是很容易想到的办法不过时间开销太大。publicclassFirstUniqChar{publicintfirstUniqChar(Strings){intns.length();// 外层循环每个字符作为候选for(inti0;in;i){intcount0;// 内层循环统计 s.charAt(i) 在整个字符串中出现的次数for(intj0;jn;j){if(s.charAt(i)s.charAt(j)){count;}// 剪枝一旦发现超过 1 次立即停止内层循环if(count1){break;}}if(count1){returni;}}return-1;}}哈希表思路暴力枚举的方式数据量一大时间开销太大。我们可以借助哈希表来优化。有两次遍历一次遍历存储字符串中的字符和其出现的次数一次遍历查询字符串中的字符是否唯一。将两次遍历分开而不是暴力枚举中的嵌套可以大幅减少时间复杂度。值得注意的是我们可以将字符出现的次数变为 true 或 false。true 表示该字符只出现一次false 表示出现不止一次。这样第二次遍历的时候查看字符所对应的值是否是 true 就好了。classSolution{publicintfirstUniqChar(Strings){// 哈希HashMapCharacter,BooleanmapnewHashMap();// 第一次迭代for(inti0;is.length();i){map.put(s.charAt(i),!map.containsKey(s.charAt(i)));}// 第二次迭代for(inti0;is.length();i){// true 即该元素唯一if(map.get(s.charAt(i))){returni;}}// 没有唯一元素return-1;}}数组思路这种方式的思路与哈希表一致只不过数组是对哈希表的一种优化。由于哈希表底层的数据结构对哈希表的操作会涉及到几个流程并不如数组直接根据索引直接访问元素高效。classSolution{publicintfirstUniqChar(Strings){// 数组int[]arraynewint[26];// 第一次迭代for(inti0;is.length();i){// 字符所对应的索引处元素 1array[s.charAt(i)-a];}// 第二次迭代for(inti0;is.length();i){// 找到值为 1 的字符if(array[s.charAt(i)-a]1){returni;}}// 没有唯一元素return-1;}}