algorithm - 优化数据结构实现

Question

有一连串的随机字符，如 'a''b''c''a'... 等等。在我查询的任何给定时间点，我需要获取第一个非重复字符。例如，对于输入“abca”，应返回“b”，因为 a 重复并且第一个非重复字符是“b”。

需要有两种方法，一种是插入，一种是查询。

我的解决方案是使用一个 linkedList 来存储传入的流字符。当我得到下一个字符时，我只是与所有当前字符进行比较，如果存在我不会插入到链表的末尾，否则我将插入到末尾。通过这种方法，查询将花费 O(1)，因为我将获得链表上的第一个元素，而插入将花费 O(n)，因为在最坏的情况下，我需要从第一个元素到最后一个元素进行比较。

有没有更好的表现方式？

Answer 1

要么你没有很好地解释你的算法，要么它不会返回正确的结果。在示例 a b a 中，您的算法会返回 a(因为它是链表中的第一个元素)吗？

不管怎样，这里是一个提高性能的修改。这个想法是使用从字符到(双向)链表节点的 HashMap 。该映射可用于确定字符是否已插入并快速到达所需节点。我们应该允许 map 目标(而不是列表节点)的 null 值来表示已经出现不止一次的字符。

插入方法的工作原理如下:

检查 map 是否包含当前字符 (O(1))。如果不是，则将其添加到列表的末尾并添加对 map 的引用 (O(1))。

如果字符已经在 map 中:检查指向的节点是否为 null (O(1))。如果是这样，请忽略它。如果不是，则从列表中删除指向的节点并将引用更新为 null 值 (O(1))。

总体而言，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;
    }
}