首页 > 其他 > 详细

在一个字符串中找到第一个只出现一次的字符

时间:2017-12-01 17:33:18      阅读:215      评论:0      收藏:0      [点我收藏+]

在一个字符串中找到第一个只出现一次的字符。如输入abaccdeff,则输出b。

(1)不使用额外空间,时间复杂度是O(n^2)

像冒泡排序那样,内存循环对外循环判断,比如第一个a,扫描后续元素,有a则不满足。

(2)哈希表。

k = 0; //填写哈希表时,每次设置成1就++k 
typedef struct {
    int flag;//初始化为0,第一次扫描到设置成1,再扫描到设置成2 
    int order;//初始化266,第几个设置成1的就设置成,几 
};//哈希表的结点

扫描完字符串后,就扫描哈希表:if(flag == 1 && a[ i ].order < 当前最小order索引值 )  就更新索引值。

时间复杂度是: 255 + 255 + n + 255 = O(n)

在一个字符串中找到第一个只出现一次的字符

原文:http://www.cnblogs.com/joyeehe/p/7943548.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!