任性黑裤

文章
6
资源
0
加入时间
2年10月24天

找出有序元素数组中指定元素出现的次数

题目:      找出有序数组中指定元素出现的次数,要求时间复杂度为O(lgn)      ex,      数组{0,0,0,2,3,3,3,3,3,4,5,5},0出现3次,3出现5次正如http://blog.csdn.net/yysdsyl/archive/2010/03/26/5419482.aspx所分析,先用二分查找找到指定元素,然后往两边查找的时间复杂度为O(lgn +k),其中k为查找元素出现的次数,如果次数为n,则该方法不满足要求,因时间复杂度为O(n)。但是,我们可以先找到