数字在排序数组中出现的次数
题目:统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5},由于3在这个数组中出现了4次,因此输出4.
分析:直接方法,顺序扫描数组得到出现次数。时间复杂度为O(n)。更快的方法,由于数组有序,可以用二分法得到第一个3和最后一个3的位置,就确定了出现多少次。时间复杂度为O(logn)
实现:
int GetFirstK(int* data,int length,int k,int start,int end) //得到第一个k的位置 { if(start>end) return -1; int middleIndex=(start+end)/2; int middleData=data[middleIndex]; if(middleData==k) { if((middleIndex>0&&data[middleIndex-1]!=k)||middleIndex==0) return middleIndex; else end=middleIndex-1; } else if(middleData>k) end=middleIndex-1; else start=middleIndex+1; return GetFirstK(data,length,k,start,end); } int GetLastK(int* data,int length,int k,int start,int end) //得到最后一个k的位置 { if(start>end) return -1; int middleIndex=(start+end)/2; int middleData=data[middleIndex]; if(middleData==k) { if((middleIndex<length-10&&data[middleIndex+1]!=k)||middleIndex==length-1) return middleIndex; else start=middleIndex+1; } else if(middleData<k) start=middleIndex+1; else end=middleIndex-1; return GetLastK(data,length,k,start,end); } int GetNumberOfK(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=GetLastK(data,length,k,0,length-1); if(first>-1&&last>-1) number=last-first+1; } return number; }
本文出自 “仙路千叠惊尘梦” 博客,请务必保留此出处http://secondscript.blog.51cto.com/9370042/1587763
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。