题目
在一个字符串(0<=字符串长度<=10000,全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1(需要区分大小写).
思路 + 代码
用一个LinkedHashMap统计每个字符出现的次数,同时保存顺序。然后String查找该字符第一次出现的位置。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22
| import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null || str.length()==0) return -1; char[] chs = str.toCharArray(); LinkedHashMap<Character, Integer> map = new LinkedHashMap<Character, Integer>(); int len = chs.length; for(int i=0; i<len; i++){ if(!map.containsKey(chs[i])){ map.put(chs[i], 1); }else{ map.put(chs[i], map.get(chs[i])+1); } } for(Map.Entry<Character, Integer> entry: map.entrySet()){ if(entry.getValue()==1) return str.indexOf(entry.getKey()); } return -1; } }
|
或者可以用一个数组来模拟Map。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
| import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null || str.length()==0) return -1; int[] counts = new int[256]; int len = str.length(); for(int i=0; i<len; i++){ counts[str.charAt(i)]++; } for(int i=0; i<len; i++){ if(counts[str.charAt(i)]==1) return i; } return -1; } }
|
空间复杂度可以继续优化,用两个Bitset分别表示出现一次和出现一次及以上。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28
| import java.util.*; public class Solution { public int FirstNotRepeatingChar(String str) { if(str==null || str.length()==0) return -1; int len = str.length(); char[] chs = str.toCharArray(); BitSet bs1 = new BitSet(256); BitSet bs2 = new BitSet(256); for(char c: chs){ if(!bs1.get(c) && !bs2.get(c)){ bs1.set(c); }else if(bs1.get(c) && !bs2.get(c)){ bs2.set(c); } } for(int i=0; i<len; i++){ char c = str.charAt(i); if(bs1.get(c) && !bs2.get(c)) return i; } return -1; } }
|