Java-字符串去重

Question

给定一个字符串由多种字符组成，包含了字母（现不区分大小写）数字。
请求除去重复字符之后的最终字符串！、
例如： str = "abcbcdac1210"
temp = "abcd120";

---

请问各位大神、有没有O(n) 复杂度的算法实现？

Answer 1

用伪代码描述下。O(n)很简单，就是借助于hash，遍历一边string，把重复的字符skip掉。

HashMap map;
int last; // the last element of the new array
for (int i = 0; i != string.length; ++i)
if (string[i] not in map)
put string[i] into the map;
copy string[i] to string[last];
increase last;
else // already in the map
// do nothing
end if
end for
shrink the string

Answer 2

hash应该可以做~

Answer 3

如果只是 "字母（现不区分大小写）数字", 那就是36个字符而已.

这样可以么, 一个数组X存最终结果, 一个数组Y存 已找到 的字符(如Y[0]存'a', 如果以找到, Y[0]=1; Y[1]存'b',...Y[25]存'z' ...Y[25]存'9' ). Y类似hash来用, 也可以用位图.

参考一下字符的ascii码, '0'<=>48 ... '9' <=> 57, 'a'<=>97,... 'z'<=>122. 那么从字符到Y数据下标的 映射很好处理了.

遍历输入字符串, 如果在数组Y对应 位置为0, 则存入X, 改Y对应位置为1; 否则处理下一字符.

Answer 4

用了javascript写了一下，不知有没有符合你要求：

var str="abcbc1210";
var temp="";
var arr=new Array(str.length);
arr=str.spilt("");
for(var i=0;i<str.length;i++){
if(temp.indexOf(arr[i])){
temp=temp+arr[i];
}
}
alert(temp + " is the answer");