我正在研究一个关于从字符串中删除重复字符的面试问题。
朴素的解决方案实际上更难实现,即使用两个 for 循环来检查每个索引与当前索引。
我尝试了几次这个问题,第一次尝试只处理排序的字符串,即 aabbcceedfg
,即 O(n)
。
然后我意识到我可以使用 HashSet
。该方案的时间复杂度也是O(n)
,但是使用了StringBuffer
和HashSet
两个Java库类,使得空间复杂度不是那很棒。
public static String duplicate(String s) {
HashSet<Character> dup = new HashSet<Character>();
StringBuffer string = new StringBuffer();
for(int i = 0; i < s.length() - 1; i++) {
if(!dup.contains(s.charAt(i))){
dup.add(s.charAt(i));
string.append(s.charAt(i));
}
}
return string.toString();
}
我想知道 - 这个解决方案是否适合技术面试?如果它不是最优的,那么更好的方法是什么?
我在谷歌上搜索了很多关于这个问题的最佳解决方案,但是,大多数解决方案使用了太多 Java 特定的库,这些库在面试环境中完全无效。
最佳答案
您无法改进复杂性,但可以在保持相同复杂性的同时优化代码。
- 使用 BitSet 而不是 HashSet(或者甚至只是一个
boolean[]
)——只有 65536 个不同的字符,适合 8Kb。每一位代表“你是否见过这个角色”。 - 将 StringBuffer 设置为指定大小 - 非常小的改进
- 错误修复:您的 for 循环结束于
i < s.length() - 1
但它应该结束于i < s.length()
, 否则它将忽略字符串的最后一个字符。
-
public static String duplicate(String s) {
BitSet bits = new BitSet();
StringBuffer string = new StringBuffer(s.length());
for (int i = 0; i < s.length(); i++) {
if (!bits.get(s.charAt(i))) {
bits.set(s.charAt(i));
string.append(s.charAt(i));
}
}
return string.toString();
}
关于java - 从未排序的字符串中删除重复项的最佳解决方案,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32643841/