Нахождение первого неповторяющегося символа в строке относительно Big O

Question

Я решил задачу по поиску первого неповторяющегося символа. Например, при вводе «apple» ответом будет «a», первый символ, который не повторяется. Хотя «е» не повторяется, это не первый символ. Другой пример: ответ «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);
}

Я хочу упростить этот код из-за вложенности l oop, имеющей сложность 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);
}

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

Смотрите это решение. Как и выше @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);
    }
}