数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符 - 数据结构 - 机器学习
1240 人阅读 | 时间：2021年01月15日 01:04
去获取百度分享代码
数据结构 - 机器学习
深度学习
当前位置：首页 » 数据结构精品文章 » 正文
数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符
1506 人参与 2018年08月18日 09:01 分类 : 数据结构精品文章 评论
问题描述：
在某个字符串中（字符串可能很长，比如有几千万个字符），请找出某个出现频率大于50%的那个字符。例如：在字符串"aabcdaa"中，字符串长为7，字符'a'出现了4次，其出现频率大于50%，因此'a'就是最终要输出的字符。
问题分析：
思路1：
解决这个问题最简单的方法就是遍历一遍字符串，针对每个字符都统计出其出现的次数，最后再遍历一遍这些次数，看哪个字符的次数超过了总次数的50%。该方法的优点是思路简单明了，缺点是额外的存储空间耗费大，算法时间复杂度高。
思路2：首先对这个字符串中的字符按照某种次序排序（比如字符的字典序），得到一个有序的字符串，显而易见，该字符串中间的那个字符一定就是我们要找的那个出现频率超过50%的字符。该方法的优点是可以在O（Nlog2N+1）时间内解决，但仍然不够快。
思路3：能否不排序呢？当然可以！我们对整个字符串遍历一遍，遍历的过程中，每当遇到两个不同的字符时，就把它们两个都删除掉，这样，最终当字符串中没有不同字符（即只有种字符）时，剩下的这种字符一定就是我们所要求的出现频率超过50%的那个字符了。比如在字符串"aabcdaa"中，我们将"ab"，"cd"分别删除，最终字符串中剩下的都是字符"a"了，"a"即为所求。
代码如下：
//在字符串中找到出现频率大于50%的那个字符
char get_char(char *ch)
{
char str;
int times = 0;
while(*ch)
{
if(times == 0)
str= *ch, times = 1;
else
{
if(str== *ch)
times++;
else
times--;
}
ch++;
}
return str;
}某个字符str如果出现频率大于一半，比如出现频率为55%，那么其他字符出现频率的总和为（1-55%）=45%，字符str出现频率比其他字符出现频率的总和大（55%-45%）=10%,按照上述我们的程序思路，在最坏的情况下，每次抵消的两个字符中都有一个str，那么最终还能剩10%的字符str。该算法的时间复杂度为O（n）。
问题扩展：
在一个int型数组中，某三个数字出现频率分别大于25%，请找出这三个数字。
思路：
和原问题大同小异，只要降低规模即可，每次抵消四个不相同的数字，不断重复，最后剩下的三个数字就是答案。
代码如下：
int candiA = 0, candiB = 0, candiC = 0;
void get_three_num(int num[])
{
int countA = 0, countB = 0, countC = 0;
for (int i = 0; i < num.Length; i++)
{
if (countA == 0 || countB == 0 || countC == 0 )
{
if (countA == 0)
{
if (countB != 0 && num[i] == candiB)
countB++;
else if (countC != 0 && num[i] == candiC)
countC++;
else
{
candiA = num[i];
countA++;
}
}
else if (countB == 0)
{
if (countA != 0 && num[i] == candiA)
countA++;
else if (countC != 0 && num[i] == candiC)
countC++;
else
{
candiB = num[i];
countB++;
}
}
else if (countC == 0)
{
if (countA != 0 && num[i] == candiA)
countA++;
else if (countB != 0 && num[i] == candiB)
countB++;
else
{
candiC = num[i];
countC++;
}
}
}
else
{
if (num[i] == candiA)
countA++;
else if (num[i] == candiB)
countB++;
else if (num[i] == candiC)
countC++;
else
{
countA--;
countB--;
countC--;
}
}
}
}来源：我是码农，转载请保留出处和链接！
本文链接：http://www.54manong.com/?id=13
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646208",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646147",
container: s
});
})();
window._bd_share_config={"common":{"bdSnsKey":{},"bdText":"","bdMini":"2","bdPic":"","bdStyle":"0","bdSize":"16"},"share":{},"image":{"viewList":["qzone","tsina","tqq","renren","weixin"],"viewText":"分享到：","viewSize":"16"},"selectShare":{"bdContainerClass":null,"bdSelectMiniList":["qzone","tsina","tqq","renren","weixin"]}};with(document)0[(getElementsByTagName('head')[0]||body).appendChild(createElement('script')).src='http://bdimg.share.baidu.com/static/api/js/share.js?v=89860593.js?cdnversion='+~(-new Date()/36e5)];
数据结构习题解析 微信号：qq444848023 QQ号：444848023
加入【我是码农】QQ群：864689844（加群验证：我是码农）
- 数组操作2018-09-10 21:35
- 栈的相关定义2018-09-03 22:34
- 各种排序方法的介绍与比较2018-09-03 23:14
- 什么是算法? 算法的5个基本特性是什么? 算法设计的要求？2018-08-18 09:04
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646186",
container: s
});
})();
(function() {
var s = "_" + Math.random().toString(36).slice(2);
document.write('');
(window.slotbydup = window.slotbydup || []).push({
id: "u3646175",
container: s
});
})();
搜索
网站分类
- 数据结构
- 数据结构视频教程
- 数据结构练习题
- 数据结构试卷
- 数据结构习题解析
- 数据结构电子书
- 数据结构精品文章
- 区块链
- 区块链精品文章
- 区块链电子书
- 大数据
- 大数据精品文章
- 大数据电子书
- 机器学习
- 机器学习精品文章
- 机器学习电子书
- 面试笔试
- 物联网/云计算
标签列表
- 数据结构 (39)
- 数据结构电子书 (20)
- 数据结构习题解析 (8)
- 数据结构试卷 (10)
- 区块链是什么 (261)
- 数据结构视频教程 (31)
- 大数据技术与应用 (12)
- 百面机器学习 (14)
- 机器学电子书 (29)
- 大数据电子书 (37)
- 程序员面试 (10)
- RFID (21)
最近发表
- 找出数组中有3个出现一次的数字
- 《百面机器学习》电子书下载
- 区块链精品电子书《深度探索区块链：Hyperledger技术与应用_区块链技术丛书》张增骏
- 区块链精品电子书《比特币：一个虚幻而真实的金融世界》
- 区块链精品电子书《图说区块链》-徐明星 & 田颖 & 李霁月
- 区块链精品电子书《是非区块链：技术、投机与泡沫》-英国《金融时报》
- 区块链精品电子书《商业区块链：开启加密经济新时代》-威廉·穆贾雅
- 区块链精品电子书《人工智能时代，一本书读懂区块链金融 (互联网_时代企业管理实战系列)》-马兆林
-
(function(){
var bp = document.createElement('script');
var curProtocol = window.location.protocol.split(':')[0];
if (curProtocol === 'https'){
bp.src = 'https://zz.bdstatic.com/linksubmit/push.js';
}
else{
bp.src = 'http://push.zhanzhang.baidu.com/push.js';
}
var s = document.getElementsByTagName("script")[0];
s.parentNode.insertBefore(bp, s);
})();
全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试
var cnzz_protocol = (("https:" == document.location.protocol) ? "https://" : "http://");document.write(unescape("%3Cspan id='cnzz_stat_icon_1276413723'%3E%3C/span%3E%3Cscript src='" + cnzz_protocol + "s23.cnzz.com/z_stat.php%3Fid%3D1276413723%26show%3Dpic1' type='text/javascript'%3E%3C/script%3E"));本站资源大部分来自互联网，版权归原作者所有！
©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任
来源：ZhiKuGroup博客，欢迎分享。
评论专区