java查找字符串中与大O相关的第一个非重复字符

Question

我解决了一个关于找到第一个非重复字符的任务。例如，如果输入“apple”，答案将是“a”，即第一个不重复的字符。即使“e”不重复，它也不是第一个字符。另一个例子：“lalas”的答案是“s”

public static char firstNonRepeatingCharacter(String input) {
    boolean unique;
    int count = input.length();
    char[] chars = input.toCharArray();
    for (int i = 0; i < input.length(); i++) {
        unique = true;
        for (int j = 0; j < input.length(); j++) {
            count--;
            char c = chars[i];
            if (i != j && c == chars[j]) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return input.charAt(i);
        }
    }
    return (0);
}

由于嵌套循环具有O（n²）复杂性，我希望简化此代码。我一直在看代码，试图找出我是否可以使它更快，但没有想到什么

Answer 1

另一种方法是查找字符的第一个和最后一个indexOf。如果两者相同，那么它是唯一的

public static char firstNonRepeatingCharacter(String input) {
    for(char c:input.toCharArray())
        if(input.indexOf(c) == input.lastIndexOf(c))
            return c;
    return (0);
}

编辑：

或使用Java 8+

return (char) input.chars()
                   .filter(c -> input.indexOf(c) == input.lastIndexOf(c))
                   .findFirst().orElse(0);

Answer 2

O（n）更好

使用中间层结构来处理重复次数

public static char firstNonRepeatingCharacter(String input) {
    boolean unique;
    int count = input.length();
    char[] chars = input.toCharArray();
    for (int i = 0; i < input.length(); i++) {
        unique = true;
        for (int j = 0; j < input.length(); j++) {
            count--;
            char c = chars[i];
            if (i != j && c == chars[j]) {
                unique = false;
                break;
            }
        }
        if (unique) {
            return input.charAt(i);
        }
    }
    return (0);
}

public static char firstNonRepeatingCharacterMyVersion(String input) {
    Map<String,Integer> map = new HashMap();
    // first iteration put in a map the number of times a char appears. Linear O(n)=n
    for (char c : input.toCharArray()) {
        String character = String.valueOf(c);
        if(map.containsKey(character)){
            map.put(character,map.get(character) + 1);
        } else {
            map.put(character,1);
        }
    }
    // Second iteration look for first element with one element.
    for (char c : input.toCharArray()) {
        String character = String.valueOf(c);
        if(map.get(character) == 1){
            return c;
        }
    }
    return (0);

}




    public static void main(String... args){
    System.out.println(firstNonRepeatingCharacter("potatoaonionp"));
    System.out.println(firstNonRepeatingCharacterMyVersion("potatoaonionp"));

}

Answer 3

private static int Solution(String s) {
        
        // to check is values has been considered once
        Set<String> set=new HashSet<String>(); 
        
        // main loop
        for (int i = 0; i < s.length(); i++) {
            String temp = String.valueOf(s.charAt(i));

            //rest of the values
            String sub=s.substring(i+1);
                if (set.add(temp) && !sub.contains(temp)) {
                    return i;
                }
        }
        return -1;
    }

Answer 4

看看这个解决方案。与上面的@Lucbel类似。基本上，使用LinkedList。我们存储所有非重复数据。但是，我们将使用更多的空间。但运行时间为O（n）

import java.util.LinkedList;
import java.util.List;

public class FirstNone {

    public static void main(String[] args) {

        System.out.println(firstNonRepeatingCharacter("apple"));
        System.out.println(firstNonRepeatingCharacter("potatoaonionp"));
        System.out.println(firstNonRepeatingCharacter("tksilicon"));

    }

    public static char firstNonRepeatingCharacter(String input) {

        List<Character> charsInput = new LinkedList<>();

        char[] chars = input.toCharArray();

        for (int i = 0; i < input.length(); i++) {

            if (charsInput.size() == 0) {
                charsInput.add(chars[i]);

            } else {

                if (!charsInput.contains(chars[i])) {
                    charsInput.add(chars[i]);
                } else if (charsInput.contains(chars[i])) {

                    charsInput.remove(Character.valueOf(chars[i]));
                }
            }

        }

        if (charsInput.size() > 0) {
            return charsInput.get(0);

        }
        return (0);
    }
}