java - 从未排序的字符串中删除重复项的最佳解决方案

Question

我正在研究一个关于从字符串中删除重复字符的面试问题。

朴素的解决方案实际上更难实现，即使用两个 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 特定的库，这些库在面试环境中完全无效。

Answer 1

您无法改进复杂性，但可以在保持相同复杂性的同时优化代码。

1. 使用 BitSet 而不是 HashSet(或者甚至只是一个 boolean[] )——只有 65536 个不同的字符，适合 8Kb。每一位代表“你是否见过这个角色”。
2. 将 StringBuffer 设置为指定大小 - 非常小的改进
3. 错误修复:您的 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();
}