
AcWing 64 字符流中第一个只出现一次的字符
发布日期:2021-05-28 16:30:51
浏览次数:29
分类:精选文章
本文共 530 字,大约阅读时间需要 1 分钟。
代码实现思路:
为了实现这个问题,我们可以使用双指针法来高效地处理字符流中的插入和查询操作。以下是详细的代码实现步骤:
初始化变量:
- 使用一个变量
res
来记录当前第一个只出现一次的字符,初始值设为'#'
。 - 使用一个字符串
s
来记录插入的字符流。 - 使用一个无序集合
map
来记录字符的出现次数,其中键是字符,值是出现次数。
插入字符:
- 每次插入一个字符
ch
,首先更新其在map
中的计数器。 - 如果计数器增加到 1:
- 如果当前
res
是'#'
,则更新res
为ch
。 - 将
ch
添加到字符串s
的末尾。
- 如果当前
- 如果计数器增加到大于 1:
- 如果当前
res
等于ch
,则使用指针p
来找到下一个只出现一次的字符。 - 移动指针
p
直到找到出现次数为 1 的字符,或者字符串末尾。 - 如果指针
p
到达字符串末尾且没有找到,只更新res
为'#'
。
- 如果当前
查询第一个只出现一次的字符:
- 直接返回
res
。如果res
是'#'
,则表示没有字符出现一次。
这个方法确保每次插入操作的时间复杂度为 O(1),在大多数情况下,查找操作的时间复杂度为 O(n),但由于每次只处理必要的移动,最终整体复杂度接近线性。这种方法可以高效地处理动态插入的字符流问题。
发表评论
最新留言
哈哈,博客排版真的漂亮呢~
[***.90.31.176]2025年04月18日 05时44分49秒
关于作者

喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
MFC 自定义消息发送字符串
2019-03-12
Linux操作系统的安装与使用
2019-03-12
C++ 继承 详解
2019-03-12
OSPF多区域
2019-03-12
Docker入门之-镜像(二)
2019-03-12
数据结构——链表(3)
2019-03-12
socket模块和粘包现象
2019-03-12
去了解拉绳位移编码器的影响因素
2019-03-12
无法初始化Winsock2.2处理
2019-03-12
vMotion 操作失败进度卡在14% ,报错: Operation Timed out
2019-03-12
重置UAG Application admin密码
2019-03-12
Horizon Daas租户管理平台扩展分配时报:内部错误
2019-03-12
项目计划甘特图绘制说明
2019-03-12
嵌入式系统试题库(CSU)
2019-03-12
【自考】之信息资源管理(一)
2019-03-12
setup facatory9.0打包详细教程(含静默安装和卸载)
2019-03-12
ionic4 路由跳转传值
2019-03-12
pwn题shellcode收集
2019-03-12
Linux kernel pwn --- CSAW2015 StringIPC
2019-03-12