剑指offer 面试题38—数字在排序数组中出现的次数
题目:
统计一个数字在排序数组中出现的次数。例如输入排序数组{1,2,3,3,3,3,4,5}和数字3,由于3在这个数组中出现了4次,因此输出4.
解法一:O(n)
顺序遍历
解法二:O(logn)
用二分查找,分别找出第一个3,和最后一个3的位置,然后计算个数。
#include <stdio.h> 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) { 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) { 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) 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); printf("first:%d\n",first); int last=GetLastK(data,length,k,0,length-1); printf("last:%d\n",last); if(first > -1 && last > -1) number =last - first +1; } return number; } void main() { int a[8]={1,2,3,3,3,3,4,5}; int result=GetNumberOfK(a,8,3); printf("%d\n",result); }
郑重声明:本站内容如果来自互联网及其他传播媒体,其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享,并不代表本站赞同其观点和对其真实性负责,也不构成任何其他建议。