首页
外语
计算机
考研
公务员
职业资格
财经
工程
司法
医学
专升本
自考
实用职业技能
登录
考研
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求: 说明你所设计算法的时间复杂度与空间复杂度。
admin
2014-04-17
57
问题
设一个字符串除字符串结束符之外,共包含n(n>1)个字符,设计一个在时间和空间两方面尽可能高效的算法,在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd,则输出c。要求:
说明你所设计算法的时间复杂度与空间复杂度。
选项
答案
时间复杂度分析:在整个算法过程中,遍历了两遍字符串,所以时间复杂度为O(n)。 空间复杂度分析:算法中使用了一个长度为256的数组,而此数组的长度不随字符串的长度增加而增加,恒为256这个常数,所以空间复杂度为O(n)。
解析
转载请注明原文地址:https://kaotiyun.com/show/7exi777K
本试题收录于:
计算机408题库学硕统考专业分类
0
计算机408
学硕统考专业
相关试题推荐
表明第一次国共合作全面破裂的事件是()。
“文化大革命”发动的两个纲领性文件是()。
20世纪初,革命派与改良派论战的中心问题是()。
古希腊是西方文明的发源地,古希腊雅典的民主政治则开启了西方民主制度的先河。下列关于雅典民主政治的说法,符合史实的有()。①民主政治时期的雅典没有国王②公民大会是雅典国家的最高决策机构③伯里克利时期,雅典民主政治达到了顶峰④包
二战后,美国以经济手段扶植和控制西欧的表现是()。
我国古代文献中记载了许多有关部落和部落联盟之间发生大规模战争的传说,如炎帝和黄帝两个部落曾战于(),结果黄帝取得了胜利。
《马可波罗行纪》中载:“此汗八里大城之周围,约有城市二百,位置远近不等,每城皆有商人来此买卖货物,盖此城为商业繁荣之城也。”“此城”指的是()。
火的使用,是人类在征服自然的进程中所取得的伟大成果。人类开始使用天然火是在()。
如下图所示为一个网络连接的示意图,主机1到主机2采用了SLIP网络连接,SLIP网络可以传输的最大数据段是296字节,主机2和主机3使用了以太网连接。请问:(1)为了使IP不分片,主机1可以在TCP包中承载多少数据?(2)主机3可以在TCP包中承载多
高度为7的AVL树最少有()个结点。
随机试题
给予行政机关公务员处分,对于案情复杂或者遇有其他特殊情形的,办案期限可以延长,但是最长不得超过____个月。
皮损具有鼠尿臭味的是:皮损愈后遗留永久性秃发的是:
A.急性淋巴细胞白血病B.急性粒细胞白血病C.急性粒-单核细胞白血病D.急性巨核细胞白血病E.急性单核细胞白血病DIC最常发生于
男性,30岁。左侧面部切割伤48小时。创口无明显化脓性感染和组织坏死。正确的处理方法是
某研究者,为了验证氯霉素对伤寒的疗效,在408例伤寒患者中进行对照试验,其中251例用氯霉素治疗,其余157例不用。结果使用组251人中死亡20人,死亡率7.07%。未用组157人中死亡36人,死亡率22.8%,已有结论被亲自证实受试者在临床医学研究中
下列关于UCITS指令的说法,错误的是()。
保险和慈善的相同点是()。
某县人民检察院在对本县的一起涉嫌强奸犯罪案的审企中,认为公安机关提出的不立案理由不能成立,遂依法向公安机关发出了立案通知书。公安机关接到通知后,()。
下列有关正义的说法,不正确的是()。
Completetheflow-chartbelow.WriteNOMORETHANTHREEWORDSforeachanswer.
最新回复
(
0
)