算法：去除字符串中的重复字母

问题：去除字符串中的重复字符，不能使用额外空间（1或者2个变量除外）。

很简单的练手题,但是发现很难写正确。

public class DuplicateChar {
	//return length of the final string
	public static int removeDuplicateChar(char []str){
		int len = str.length;
		if(len < 2) return len;
		for(int i=0;i<len-1;i++){
			char ch = str[i];
			int index = i+1;
			for(int j=i+1;j<=len-1;){
				
				if(ch == str[j]){				
					j++;					
				}else {
					if(j!=index){
						str[index] = str[j];						
					}
					j++; index++;					
				}
			}
			len = index;
		}
		return len;
	}
	public static void test(char []str){
		int len = removeDuplicateChar(str);
		for(int i=0;i<len;i++){
			System.out.print(str[i] + "\t");
		}
		System.out.println();
	}
	/**
	 * @param args
	 */
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		char [] str1 = {'a', 'b'};
		char [] str2 = {'a', 'b','c','a','a','e','f','a'};  
		char [] str3 = {'a'};
		char [] str4 = {};
		test(str1);
		test(str2);
		test(str3);
		test(str4);
	}

}

评论

2 楼 standalone 2012-11-07  

那就是使用额外空间了吧？

1 楼 citystreet 2012-11-07  

可以使用hashset来做 简单点