оптимизация реализации структуры данных

Question

Существует поток случайных символов, похожих на 'a''b''c''a' ... и так далее. В любой момент времени, когда я запрашиваю, мне нужно получить первый не повторяющийся символ. Например, для ввода «abca» «b» должно быть возвращено, так как a повторяется, а первым не повторяющимся символом является «b».

Должно быть два метода: один для вставки и один для запроса.

Мое решение состоит в том, чтобы иметь связанный список для хранения входящих символов потока. Пока я получаю следующий символ, я просто сравниваю его со всеми текущими символами, и если он присутствует, я не буду вставлять в конец связанного списка, иначе я вложу его в конец. При таком подходе запрос будет принимать O (1), так как я получу первый элемент в связанном списке, а вставка возьмет O (n), так как мне нужно сравнить от первого элемента до последнего элемента в худшем случае.

Есть ли лучший способ?

Answer 1

Либо вы не хорошо объяснили свой алгоритм, либо он не вернет правильный результат. В примере a b a ваш алгоритм вернет a (потому что это первый элемент в связанном списке)?

В любом случае, это модификация, которая повышает производительность. Идея состоит в том, чтобы использовать хэш-карту из символов в (дважды) связанные узлы списка. Эта карта может использоваться, чтобы определить, был ли уже вставлен символ и быстро добраться до требуемого узла. Мы должны разрешить значение null для цели карты (вместо узла списка), чтобы выразить символ, который уже неоднократно повторялся.

Способ вставки работает следующим образом:

Проверить, если карта содержит текущий символ (O (1)). Если нет, добавьте его в конец списка и добавьте ссылку на карту (O (1)).

Если символ уже находится на карте: проверьте, указан ли указательный узел null (O (1)). Если это так, просто игнорируйте его. Если это не так, удалите указанный узел из списка и обновите ссылку на значение null (O (1)).

В целом, a O (1) операция.

Запрос работает так же, как и в предыдущем решении.

Настоящая реализация C#. Это, по сути, перевод 1: 1 приведенного выше объяснения:

class StreamAnalyzer 
{ 
    LinkedList<char> characterList = new LinkedList<char>(); 
    Dictionary<char, LinkedListNode<char>> characterMap 
     = new Dictionary<char, LinkedListNode<char>>(); 

    public void AddCharacter(char c) 
    { 
     LinkedListNode<char> referencedNode; 
     if (characterMap.TryGetValue(c, out referencedNode)) 
     { 
      if(referencedNode != null) 
      { 
       characterList.Remove(referencedNode); 
       characterMap[c] = null; 
      } 
     } 
     else 
     { 
      var node = new LinkedListNode<char>(c); 
      characterList.AddLast(node); 
      characterMap.Add(c, node); 
     } 
    } 

    public char? GetFirstNonRepeatingCharacter() 
    { 
     if (characterList.First == null) 
      return null; 
     else 
      return characterList.First.Value; 
    } 
}