查找字符串中的第一个非重复字符

Question

我正在编写一种方法来查找字符串中的第一个非重复字符。我在之前的stackoverflow问题中看到了这个方法

public static char findFirstNonRepChar(String input){
 char currentChar = '\0';
 int len = input.length();
 for(int i=0;i<len;i++){
    currentChar = input.charAt(i);
    if((i!=0) && (currentChar!=input.charAt(i-1)) && (i==input.lastIndexOf(currentChar))){
        return currentChar;
    }
 }
 return currentChar;
}

我想出了一个使用哈希表的解决方案，其中我有两个 for 循环（未嵌套），我在一个循环中遍历字符串，写下字母的每次出现（例如在苹果中，a 有 1，p 有 2等）然后在第二个循环中，我遍历哈希表以查看哪个首先计数为 1。与我想出的方法相比，上述方法有什么好处？我是 Java 的新手，确实有两个循环（不是嵌套的）会阻碍时间复杂度。这两种算法都应该有 O(n) 对吧？对于这个问题，有没有比这两个解决方案更快、空间复杂度更低的算法？

原文由 Jonathan Bishop 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

正如您询问您的代码是否来自 O(n) 或不是，我认为不是，因为在 for 循环中，您正在调用 lastIndexOf 最坏的情况是 O(n) 。所以它来自 O(n^2) 。

关于你的第二个问题：有两个没有嵌套的循环，也来自 O(n) 。

如果假设输入字符串中有非 unicode 字符，并且假设大写或小写字符不同，则以下将使用 o(n) 执行并支持从 0 到 255 的所有 ASCII 代码 --- :

 public static Character getFirstNotRepeatedChar(String input) {

    byte[] flags = new byte[256]; //all is initialized by 0

    for (int i = 0; i < input.length(); i++) { // O(n)
        flags[(int)input.charAt(i)]++ ;
    }

    for (int i = 0; i < input.length(); i++) { // O(n)
        if(flags[(int)input.charAt(i)] > 0)
            return input.charAt(i);
    }

    return null;
}

感谢 Konstantinos Chalkias 关于溢出的提示，如果您的输入字符串中某个字符的出现次数超过 127 次，您可以将 flags 数组的类型从 byte[] 更改为 int[] 或 long[] 以防止溢出 byte 类型。

希望它会有所帮助。

原文由 STaefi 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

public class FirstNonRepeatCharFromString {

    public static void main(String[] args) {

        String s = "java";
        for(Character ch:s.toCharArray()) {
            if(s.indexOf(ch) == s.lastIndexOf(ch)) {
                System.out.println("First non repeat character = " + ch);
                break;
            }
        }
    }
}

原文由 Jayaraj Chevery 发布，翻译遵循 CC BY-SA 4.0 许可协议