设一个字符串除字符串结束符之外，共包含n(n＞1)个字符，设计一个在时间和空间两方面尽可能高效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd，则输出c。要求：给出算法的基本设计思想。

admin2014-04-17 37

问题设一个字符串除字符串结束符之外，共包含n(n＞1)个字符，设计一个在时间和空间两方面尽可能高效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd，则输出c。要求：
给出算法的基本设计思想。

选项

答案基本设计思想：算法的策略是构建一个简单的散列表，由于本题需要构建的是字符的散列表，而一个字符(Char)占8个二进制位，符出现的次数。这样就创建了一个大小为256，以字符ASCⅡ码为键值的散列表。当第一遍遍历这个数组时，每碰到一个字符，在散列表中找到对应的项并把出现的次数增加一次。第一遍遍历完后，进行第二遍遍历，就能直接从散列表中得到每个字符出现的次数了。

解析

转载请注明原文地址:https://kaotiyun.com/show/sYxi777K

本试题收录于：计算机408题库学硕统考专业分类

计算机408

学硕统考专业

相关试题推荐

随机试题

最新回复(0)

设一个字符串除字符串结束符之外，共包含n(n＞1)个字符，设计一个在时间和空间两方面尽可能高效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd，则输出c。要求：给出算法的基本设计思想。

计算机408

学硕统考专业

英国发动鸦片战争的主要目的是()。

清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏

洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

罗马帝国疆域扩张到顶点是在()统治时期。

8世纪利用汉字偏旁创造日本片假名的是()。

“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

在AOE网络中关键路径叙述正确的是()。

患者，女，19岁，未婚。月经提前，量少、色红、质黏稠，伴手足心热，两颧潮红，舌红少苔，脉细数。治疗应首选

根据《建设工程质量管理条例》规定，未按照工程建设强制性标准进行勘察、设计，可以给予勘察单位或设计单位的处罚有()。

海底管道防腐蚀常采用牺牲阳极阴极保护系统，其牺牲阳极常采用()。

下列关于在线旅行服务业产生背景的说法中，错误的是()。

唐玄宗在位期间，出现了繁荣景象，这足我国古代史的哪次盛世?()

公历以耶稣基督诞生那一年作为公元元年，它始于()。

在目标实现程度的测量中,评估中测量的标准就是案主在介入阶段的完成情况。()

A、条件(1)充分，但条件(2)不充分．B、条件(2)充分，但条件(1)不充分．C、条件(1)和(2)单独不充分，但条件(1)和条件(2)联合起来充分．D、条件(1)充分，条件(2)也充分．E、条件(1)和(2)单独都不充分，条件(1)和条件(2)

一批种子中良种占，从中任取6000粒，计算这些种子中良种所占比例与之差小于0．01的概率．

Ontheall-importantquestionofpower—theefficacyofpower,themoralityofpower,thedesirabilityofpower—AmericanandEuro

设一个字符串除字符串结束符之外，共包含n(n＞1)个字符，设计一个在时间和空间两方面尽可能高效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd，则输出c。要求： 给出算法的基本设计思想。

计算机408

学硕统考专业

英国发动鸦片战争的主要目的是()。

清初设置的两个“办事大臣”是()。①宁古塔②西宁③库伦④西藏

洋务运动中翻译出《几何原本》后九卷、《代数学》、《重学》等数学、物理方面的科技书籍的翻译家是()。

刘向子刘歆继承父业，完成了这一工作，并且写出了()一书，是我国第一部目录书。

人民解放军转入战略进攻的方向为大别山地区，主要是由于()。①大别山战略位置重要②大别山有良好的群众基础③占据大别山可以从根本上改变战局

罗马帝国疆域扩张到顶点是在()统治时期。

8世纪利用汉字偏旁创造日本片假名的是()。

“二战”后主要资本主义国家经济恢复和发展的杠杆是()。①政府采取宏观调控政策②发展国家垄断资本主义③充分利用科技成果④加强国际经济联系

北宋在统一南方割据势力的过程中特设()，把征南所得的财富统一存放，以作日后恢复幽燕之费。

在AOE网络中关键路径叙述正确的是()。

患者，女，19岁，未婚。月经提前，量少、色红、质黏稠，伴手足心热，两颧潮红，舌红少苔，脉细数。治疗应首选

根据《建设工程质量管理条例》规定，未按照工程建设强制性标准进行勘察、设计，可以给予勘察单位或设计单位的处罚有()。

海底管道防腐蚀常采用牺牲阳极阴极保护系统，其牺牲阳极常采用()。

下列关于在线旅行服务业产生背景的说法中，错误的是()。

唐玄宗在位期间，出现了繁荣景象，这足我国古代史的哪次盛世?()

公历以耶稣基督诞生那一年作为公元元年，它始于()。

在目标实现程度的测量中,评估中测量的标准就是案主在介入阶段的完成情况。()

A、条件(1)充分，但条件(2)不充分．B、条件(2)充分，但条件(1)不充分．C、条件(1)和(2)单独不充分，但条件(1)和条件(2)联合起来充分．D、条件(1)充分，条件(2)也充分．E、条件(1)和(2)单独都不充分，条件(1)和条件(2)

一批种子中良种占，从中任取6000粒，计算这些种子中良种所占比例与之差小于0．01的概率．

Ontheall-importantquestionofpower—theefficacyofpower,themoralityofpower,thedesirabilityofpower—AmericanandEuro

设一个字符串除字符串结束符之外，共包含n(n＞1)个字符，设计一个在时间和空间两方面尽可能高效的算法，在这个字符串中找到第一个只出现一次的字符。例如字符串为abcdabd，则输出c。要求：给出算法的基本设计思想。