AcWing 64 字符流中第一个只出现一次的字符
发布日期:2021-05-28 16:30:51 浏览次数:29 分类:精选文章

本文共 530 字,大约阅读时间需要 1 分钟。

代码实现思路:

为了实现这个问题,我们可以使用双指针法来高效地处理字符流中的插入和查询操作。以下是详细的代码实现步骤:

  • 初始化变量

    • 使用一个变量 res 来记录当前第一个只出现一次的字符,初始值设为 '#'
    • 使用一个字符串 s 来记录插入的字符流。
    • 使用一个无序集合 map 来记录字符的出现次数,其中键是字符,值是出现次数。
  • 插入字符

    • 每次插入一个字符 ch,首先更新其在 map 中的计数器。
    • 如果计数器增加到 1:
      • 如果当前 res'#',则更新 resch
      • ch 添加到字符串 s 的末尾。
    • 如果计数器增加到大于 1:
      • 如果当前 res 等于 ch,则使用指针 p 来找到下一个只出现一次的字符。
      • 移动指针 p 直到找到出现次数为 1 的字符,或者字符串末尾。
      • 如果指针 p 到达字符串末尾且没有找到,只更新 res'#'
  • 查询第一个只出现一次的字符

    • 直接返回 res。如果 res'#',则表示没有字符出现一次。
  • 这个方法确保每次插入操作的时间复杂度为 O(1),在大多数情况下,查找操作的时间复杂度为 O(n),但由于每次只处理必要的移动,最终整体复杂度接近线性。这种方法可以高效地处理动态插入的字符流问题。

    上一篇:AcWing 65 数组中的逆序对
    下一篇:AcWing 63 字符串中第一个只出现一次的字符

    发表评论

    最新留言

    哈哈,博客排版真的漂亮呢~
    [***.90.31.176]2025年04月18日 05时44分49秒