题目描述 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1.
解体思路1
最直观的解法是使用 HashMap 对出现次数进行统计，但是考虑到要统计的字符范围有限，因此可以使用整型数组代替 HashMap。
代码实现：
public class Solution {
public int FirstNotRepeatingChar(String str) {
int[] cnts = new int[256];
for(int i=0; i<str.length(); i++)
cnts[str.charAt(i)]++;
for(int i=0; i<str.length(); i++)
if(cnts[str.charAt(i)] == 1)
return i;
return -1;
}
}
解体思路2
以上实现的空间复杂度还不是最优的。考虑到只需要找到只出现一次的字符，那么我们只需要统计的次数信息只有 0,1,更大，使用两个比特位就能存储这些信息。
代码实现:
import java.util.BitSet;
public class Solution {
public int FirstNotRepeatingChar(String str) {
BitSet bs1 = new BitSet(256);
BitSet bs2 = new BitSet(256);
for(char c : str.toCharArray()) {
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<str.length(); i++) {
char c = str.charAt(i);
if(bs1.get(c) && !bs2.get(c))
return i;
}
return -1;
}
}