获取一个字符串中的第一个不重复字符

public class firstNonRepeated {
	public static void main(String[] args) {
		String str = "tttts33sssaaa5aabtbbzz5Z";
		int strLength = str.length();
		str += str;
		for (int index = 0; index < strLength; index++) {
			int i = str.indexOf(str.charAt(index), index + 1);
			if (i > strLength && i == strLength + index) {
				System.out.println(str.charAt(index));
				return;
			}
		}
		System.out.println("没有不重复的字符");
	}
}

还有更好的吗？刚刚看到另外一篇博文的方法是利用的HashTable，我觉得这个算法应该要更好吧。








 

评论

3 楼 bolide74 2011-04-14  

cq062364 写道

可以用一个长度为128的int数组作为一个hash表，然后遍历整个字符串，以每个字符的ascii值作为key，以该字符出现的次数为value，最后再次遍历一遍这个数组，将只出现一次的字符找出来。要找出第一个不重复字符，在遍历的时候最好存一下每个字符的索引，找出索引最小的即可。不知道我说明白了没有，如果这个算法有问题请楼主不吝赐教。

这个方法也是可以的，不过复杂度有点大。
我看到另外一个利用HashTable容器的算法，是轮询字符串，然后依次先get一下HashTable是否已经有这个字符了，如果有了就把对应的value值设为2，如果没有就把这个字符put进去。最后再轮询HashTable找出第一个value是2的字符。
思路跟你是一样的，只不过他直接用的hashtable容器，没有用二维数组。

2 楼 cq062364 2011-04-14  

import java.io.*;

public class Test{
public static int search(String str){
int[][] a=new int[128][2];
int length=str.length();
for(int i=0;i<length;i++){
int j=(int)str.charAt(i);
a[j][0]++;
a[j][1]=i;
}
int minIndex=128;
for(int i=0;i<128;i++){
if(a[i][0]==1){
if(minIndex>a[i][1]){
minIndex=a[i][1];
}
}
}
return minIndex;
}

public static void main(String[] args){
BufferedReader br=null;
String str=null;
while(true){
try{
br=new BufferedReader(new InputStreamReader(System.in));
str=br.readLine();
}catch(Exception e){
e.printStackTrace();
}
int result=search(str);
if(result==128){
System.out.println("没有不重复的字符");
}else{
System.out.println(str.charAt(result));
}
}
}
}

1 楼 cq062364 2011-04-14  

可以用一个长度为128的int数组作为一个hash表，然后遍历整个字符串，以每个字符的ascii值作为key，以该字符出现的次数为value，最后再次遍历一遍这个数组，将只出现一次的字符找出来。要找出第一个不重复字符，在遍历的时候最好存一下每个字符的索引，找出索引最小的即可。不知道我说明白了没有，如果这个算法有问题请楼主不吝赐教。