剑指offer之面试题38数字在排序数组中出现的次数

古城微笑少年丶 2022-07-24 04:05 115阅读 0赞

**问题描述**：

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

例如：

输入排序数组\{1,2,3,3,3,4,5\}和数字3，由于3在这个数组中出现了4次，因此输出4。

**实现代码**如下：

#include <stdio.h>
    #include <stdlib.h>
    #include <stdbool.h>
    #include <limits.h>
    
    int findLastK(int *num,int left,int right,int len,int k){
    	if(left>right){
    		return -1;
    	}
    	int mid = (left+right)/2;
    	int middate =num[mid];
    	
    	if(middate==k){
    		if((mid<len && num[mid+1]!=k) || mid == len){
    			return mid;
    		}else{
    			left = mid+1;
    		}
    	}else if(middate>k){
    		right=mid-1;
    	}else if(middate<k){
    		left=mid+1;
    	}
    	return findLastK(num,left,right,len,k);
    }
    
    int findFirstK(int *num,int left,int right,int len,int k){
    	if(left>right){
    		return -1;
    	}
    	int mid = (left+right)/2;
    	int middate =num[mid];
    	
    	if(middate==k){
    		if((mid>0 && num[mid-1]!=k) || mid == 0){
    			return mid;
    		}else{
    			right = mid-1;
    		}
    	}else if(middate>k){
    		right=mid-1;
    	}else if(middate<k){
    		left=mid+1;
    	}
    	return findFirstK(num,left,right,len,k);
    }
    
    
    int getNumberOfK(int *num,int len,int k){
    	int rs = 0;
    	if(num!=NULL && len >0){
    		int last =findLastK(num,0,len-1,len,k);
    		int first=findFirstK(num,0,len-1,len,k);
    		if(last>-1 && first>-1){
    			rs = last -first+1;
    		}
    	}
    	return rs;
    }
    
    int main(int argc, char *argv[])
    {
    	int num[]={
    		1,2,3,3,3,3,4
    	};
    	int k ;
    	scanf("%d",&k);
    	int len = sizeof(num)/sizeof(int);
    	int rs =getNumberOfK(num,len,k);
    	printf("%d\n",rs);
    	return 0;
    }

**参考资料**：  
剑指offer  
  
**备注**：  
转载请注明出处：http://blog.csdn.net/wsyw126/article/details/51383949  
作者：WSYW126