Как найти первый неповторяющийся / уникальный символ (или URL) в строке (или в большом файле)

Question

Это вопросы интервью. Я изо всех сил пытался придумать желаемое решение, но пока безуспешно!

Подход времени O (n ^ 2) довольно очевиден с пробелом O (1), где n - длина строки / общее количество URL.

Может быть достигнуто решение O (n), которое требует дополнительного места. В случае неповторяющегося первого символа в строке начинайте с конца строки и сканируйте в направлении вперед. Используйте битовый массив для отслеживания того, какие значения символов произошли до сих пор. Если символ еще не виден (то есть справа от текущего индекса), установите этот символ как «вероятный неповторяющийся» символ. Это будет обновлено по мере сканирования, обработанного влево. При достижении первого индекса последним символом «не видел раньше» является результат. Для набора символов ASCII это вполне приемлемое решение; так как для этого нужен только 256-битный массив. Однако для набора символов UNICODE сложность пространства выше. В случае неповторяющегося URL-адреса в файле аналогичный подход может быть применен с использованием хэш-таблицы. Здесь большое значение имеет пространство для реализации хеширования, например хранения URL-адресов для возможных коллизий.

Я ищу лучшее решение с O (n) сложностью времени и постоянной или логарифмической пространственной сложностью. Пожалуйста, поделитесь своей идеей на языке программирования, таком как C, C ++ или Java. Спасибо.

Answer 1

Общий алгоритм более или менее очевиден (только один проход последовательности) - псевдокод, извините:)

set s
for each x in sequence
    if s.contains(x)
       return x
    else
       s.add(x)
end

Единственная оставшаяся часть - это какой набор данных выбрать.если |U| является размером домена набора (например, алфавита), то на основе ожидаемого максимального значения |s| / |U| мы решаем, использовать ли битовый вектор или хеш-таблицу.(Обратите внимание, что даже для огромного алфавита битовый вектор был бы лучше, чем хеш-таблица, если мы ожидаем появления большинства букв).

Также обратите внимание, что для использования битового вектора это подразумеваетсячто вы должны иметь возможность ранжировать элементы, то есть сопоставить их с числом в [0..n).Это просто, когда мы говорим о символах, но не для остальных типов ввода.

Answer 2

Я использую хеш-карту, чтобы получить первого неповторяющегося персонажа.

Таким образом, мы можем создать хэш-карту, последовательно считывая все символы в строке и сохраняя количество раз, которое появляется каждый символ.После того, как мы создали хеш-карту, мы можем последовательно прочитать записи, чтобы увидеть, какая из них имеет счетчик единиц.Каково время выполнения этого алгоритма?У нас есть O (n) для создания хэш-карты и другое O (n) для чтения записей.Это приводит к времени выполнения O (n) + O (n) = O (2n) = O (n).

Коды:

public static Character getNonRepeated(String str){
    Character retc = null;
    int n = 0;
    Map<Character,Integer> charCounter=new HashMap<Character,Integer>(); 

    for (int i = 0; i < str.length() ; i++){
        if (charCounter.containsKey(str.charAt(i))) {
            charCounter.put(str.charAt(i), charCounter.get(str.charAt(i))+1);                               
        }else{
            charCounter.put(str.charAt(i), 1);              
        }
    }

    for (int i = 0; i < str.length() ; i++){
        if (charCounter.get(str.charAt(i)) == 1){
            retc =  str.charAt(i);
        }
    }
    return retc;
}