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

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

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

image.png

问题描述:

在某个字符串中(字符串可能很长,比如有几千万个字符),请找出某个出现频率大于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

数据结构习题解析  

微信号:qq444848023    QQ号:444848023

加入【我是码农】QQ群:864689844(加群验证:我是码农)

<< 上一篇 下一篇 >>

网站分类

标签列表

最近发表

全站首页 | 数据结构 | 区块链| 大数据 | 机器学习 | 物联网和云计算 | 面试笔试

本站资源大部分来自互联网,版权归原作者所有!