在与 Big 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

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 2

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

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

编辑：

或者用Java8+

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

Answer 3

查看此解决方案。类似于上面的@Lucbel。基本上，使用 LinkedList。我们存储所有不重复的。但是，我们将使用更多space。但是运行时间是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);
    }
}

Answer 4

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;
    }

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

Finding first non repeating character in a string in relation to Big O

java

big-o