数字在排序数组中出现的次数「建议收藏」

数字在排序数组中出现的次数

大家好,又见面了,我是全栈君。

题目:统计一个数字在排序数组中出现的次数。

比如,输入排序数组{1,2,3,3,3,3,4,5}和数字3因为3在这个数组中出现了4次。因此输出4。
题目解法非常多。关键是要找到让人惬意的方法,直接统计当然能够。但是显然不是我们要的答案。
比較好的思路例如以下:
使用二分查找的拓展,当查找的元素有反复的时,找到元素的第一个和最后一个。

这样将能够计算出该元素有多少个反复的了。二分法在数组中查找一个合乎要求的数字时间复杂度是O(logn)。因此总的时间复杂度也仅仅有O(logn)。

//递归找到排序数组中第一个k
int GetFirstK(int *data, int length, int k, int start, int end)
{
	if(start>end)
		return -1;
	int middleIndex=(start+end)/2;
	int middleData=data[middleIndex];

	if (middleData==k)
	{
		//推断是否是第一个k
		if ((middleIndex>0&&data[middleIndex-1]!=k)||middleIndex==0)
		{
			return middleIndex;
		}
		else
		{//第一个k肯定在左边
			end=middleIndex-1;
		}
	}
	else if (middleData>k)
	{
		end=middleIndex-1;
	}
	else
		start=middleIndex+1;
	//递归
	return GetFirstK(data,length,k,start,end);
}

//相同的思路,递归找到最后的一个k
int GetEndK(int *data, int length, int k, int start, int end)
{
	if(start>end)
		return -1;
	int middleIndex=(start+end)/2;
	int middleData=data[middleIndex];

	if (middleData==k)
	{
		if ((middleIndex<length-1&&data[middleIndex+1]!=k)||middleIndex=length-1)
		{
			return middleIndex;
		}
		else
			start=middleIndex+1;
	}
	else if (middleData>k)
	{
		end=middleIndex-1;
	}
	else
	{
		start=middleIndex+1;
	}
	return GetEndK(data,length,k,start,end);
}

//计算出k在数组中出现的次数
int GetNumOfK(int *data, int length, int k)
{
	int number=0;
	if (data!=NULL&&length>0)
	{
		int first=GetFirstK(data,length,k,0,length-1);
		int last=GetEndK(data,length,k,0,length-1);
		if (first>-1&&last>-1)
		{
			return last-first+1;
		}
	}
	return number;
}

转载请注明出处:http://blog.csdn.net/lsh_2013/article/details/46367393

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115428.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • 公有云和私有云的区别有哪些

    公有云和私有云的区别有哪些近年来,云服务已经走进千百家企业,成为公司业务不可分割的一部分。作为公司管理层,我们需要使用云服务,需要对企业所使用的云服务产品做出选择,但大多数人不是科班出现,很多时候,概念都理解不了,更别提决策了。公有云、私有云、混合云,这几个概念,在企业使用云服务时,最为常见,下面我们就一起来理解一下它们,知道它们有什么区别,方便日后根据企业的实际运营状况,选择合适的云服务。公有云云计算提出的愿景,是想让企业像使用水电那样,使用IT服务。国家建立水厂、发电厂,集中提供水电,企业不再需要挖水..

  • ADRC学习心得(持续更新)[通俗易懂]

    ADRC学习心得(持续更新)[通俗易懂]两年前第一次接触到PID觉得很高深,很神奇;后来逐渐觉得单纯的PID小儿科了,又了解到专家PID,模糊PID,神经网络PID这些改进算法,再后来又知道了ADRC,便感控制领域浩如烟海,所学不过沧海一粟。然便纵真理无穷,进一寸自有一寸的欢喜。不敢说看了几篇论文,听了几节报告,做了几次仿真,就吃透ADRC了,不过只是一些粗浅的理解,记录一行歪歪斜斜的足迹。以便回首过眼云烟之时,可以安慰自己一句,我已经飞过。一、系统有关概念1、系统的状态空间模型描述一个系统,最常用的数学模型有:微分方程传递函数状

  • 范数对于数学的意义?1范数、2范数、无穷范数

    作者:JIWeiwei链接:https://www.zhihu.com/question/21868680/answer/25599956来源:知乎著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。作者:Faaany链接:https://www.zhihu.com/question/21868680/answer/136376374来源:知乎著作权归作者所有。商业转载请联系作者…

  • apache 80端口被占用_tomcat8005端口被占用

    apache 80端口被占用_tomcat8005端口被占用参考:https://jingyan.baidu.com/article/1876c8527b1fc3890b13763b.html1.win+R,输入cmd,打开命令行窗口2.命令行输入netstat-ano3.找到80端口及对应进程 4.在任务管理器中的进程处查看与上述80端口对应的PID相同的进程,并关闭。如果没有PID,选择“查看”–&gt;"选择列"–…

    2022年10月30日
  • csgo开箱网站都有哪些_csgo官方承认的开箱网站

    csgo开箱网站都有哪些_csgo官方承认的开箱网站csgo开箱网站有哪些?csgo开箱网站大全以下国内知名CSGO开箱网站网站状态优惠码/推广码官网直达链接直接取回csgogoincsgo直接取回csgogoskinsdog直接取回csgo88hash直接取回csgogoskskins直接取回csgofateskins可取回暂无yskins直接取回csgocoolkaixiang可取回csgogopiggycase以下国外知名CSGO开箱网站

  • Idea中建多层级包时出现的问题

    Idea中建多层级包时出现的问题刚开始使用idea时发现不会分包。假如我想在com下面分别建Dao、pojo、service包等,会出现每次在上一个包里面建包,并不会使Dao、pojo、service包平级。解决方法:方法一:            1)先在java包下建名为com包,     2)鼠标点击com的上一级包(这里就是java包),然后新建包为com.Dao包。这里会出现不用着急,因为你只有一个包。再继续点击com…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号