剑指offer-37-数字在数组中出现的次数
数字在排序数组中出现的次数
http://www.nowcoder.com/questionTerminal/70610bf967994b22bb1c26f9ae901fa2
思路
二分查找
找到值之后向两边扩展,找相同的值
public class Solution { public int GetNumberOfK(int [] array , int k) { //二分判断是否有k int l=0,r=array.length-1; while(l<=r){ int mid=(l+r)>>1; if(array[mid]<k){ l=mid+1; }else if(array[mid]>k){ r=mid-1; }else{ l=mid; r=mid; break; } } // l!=r说明没有找到k if(l!=r){ return 0; } int cnt=-1; while(l>=0&&array[l]==k){ l--; cnt++; } while(r<=array.length-1 && array[r]==k){ r++; cnt++; } return cnt; } }
剑指offer与数据结构 文章被收录于专栏
本专栏包括剑指offer题目和一些刷题用的数据结构,单调栈,树状数组,差分数组,后面还会更新红黑树等较为复杂的数据结构