二维码

数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符 - 数据结构 - 机器学习

1302 人阅读 | 时间：2021年01月15日 01:04
数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符 - 数据结构 - 机器学习 #daohang ul li t,.reed .riqi,a.shangg,a.xiatt,a.shangg:hover,a.xiatt:hover,a.shang,a.xiat,a.shang:hover,a.xiat:hover,.reed-pinglun-anniu,span.now-page,#daohangs-around,#caidan-tubiao,#daohangs,#daohangs li,#btnPost{background-color:#D10B04;} .dinglanyou1 h3{border-bottom:3px solid #D10B04;} #dibuer{border-top:2px solid #D10B04;}.cebianlan .rongqi h3{border-bottom:1px solid #D10B04;} #edtSearch{border:1px solid #D10B04;} #daohang .zuo ul li{border-right:1px solid #;} #daohang ul li t a{border-top:1px solid #;border-right:1px solid #D10B04;} #daohang ul li t a:hover{border-right:1px solid #;} #daohang .you ul li a:hover,#daohang .zuo ul li a:hover,.reed-pinglun-anniu:hover{background-color:#;} a:hover,.reed h6 a:hover,#dibuer a:hover,.reed .riqiding,.cebianlan .rongqi li a:hover,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.shu a,#pinglun-liebiao ul.fubens li.depth-1 dl dd span.huifuliuyan a:hover,.reed-biaoti h6 span{color:#D10B04;} .reed .kan a{color:#0A0AF5;}.reed .kan a:hover{color:#D10101;} @media screen and (max-width:1492px){a.shang,a.xiat{background:none;} a.xiat:hover,a.shang:hover{background-color:#f9f9f9;background-image:none;text-decoration:none;}} var _hmt = _hmt || [];(function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s);})(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?b19db5ba3b437a9e8698d2bc8fc64334"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?2d748c9763cfc72fb7d1ccab29f0770d"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })(); var _hmt = _hmt || []; (function() { var hm = document.createElement("script"); hm.src = "https://hm.baidu.com/hm.js?f6d451f3f1be23f3abf240c64c469c1b"; var s = document.getElementsByTagName("script")[0]; s.parentNode.insertBefore(hm, s); })();

当前位置：首页 » 数据结构精品文章 » 正文

(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646201", container: s }); })();
(function() { var s = "_" + Math.random().toString(36).slice(2); document.write('
'); (window.slotbydup = window.slotbydup || []).push({ id: "u3646162", container: s }); })();

数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符

1506 人参与  2018年08月18日 09:01  分类 : 数据结构精品文章  评论

数据结构经典面试题：在字符串中找到出现频率大于50%的那个字符 - 数据结构 - 机器学习

问题描述：

在某个字符串中（字符串可能很长，比如有几千万个字符），请找出某个出现频率大于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（加群验证：我是码农）

<< 上一篇 下一篇 >>
(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 }); })();
搜索

网站分类

标签列表

最近发表

    (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"));本站资源大部分来自互联网，版权归原作者所有！

jQuery(document).ready(function($){ /* prepend menu icon */ $('#daohangs-around').prepend('
'); /* toggle nav */ $("#caidan-tubiao").on("click", function(){ $("#daohangs").slideToggle(); $(this).toggleClass("active"); }); });

©著作权归作者所有：来自ZhiKuGroup博客作者没文化的原创作品，如需转载，请注明出处，否则将追究法律责任 来源：ZhiKuGroup博客，欢迎分享。

评论专区
  • 昵 称必填
  • 邮 箱选填
  • 网 址选填
  • 验证码
◎已有 0 人评论
相关文章
搜索
作者介绍
superadmin

superadmin

30天热门
热评文章
最近发表
标签列表

©2012-2022 Think tank 鄂ICP备19030179号-1 | 使用Chrome浏览本站最佳 | 声明：本站的文章和资源来自互联网或者站长的原创，按照 CC BY -NC -SA 3.0 CN协议发布和共享，转载或引用本站文章应遵循相同协议。 如果有侵犯版权的资源请尽快联系站长，我们会在24h内删除有争议的资源； 本站所有收费以及免费的信息和数据仅供参考，不构成投资建议，本网站不承担由此导致的任何责任。
登陆

Powered By Z-BlogPHP

本站会员尊享VIP特权，现在就加入我们吧！登录注册×
»
会员登录
新用户注册
×
会员注册
已有账号登录
×