首页 > 代码库 > [剑指Offer] 37.数字在排序数组中出现的次数
[剑指Offer] 37.数字在排序数组中出现的次数
题目描述
统计一个数字在排序数组中出现的次数。
【思路】因为是排序数组,所以可以用二分法搜索到要查找的值在数组中的一个位置,接着向两侧扫描,遇到不等的就停止。
1 class Solution { 2 public: 3 int getIndexbyDivision(vector<int> data,int k){ 4 int left = 0,right = data.size() - 1; 5 int middle = left + (right - left)/2; 6 while(left <= right){ 7 if(k > data[middle]) 8 left = middle + 1; 9 else if(k < data[middle]) 10 right = middle - 1; 11 else 12 return middle; 13 middle = left + (right - left)/2; 14 } 15 return -1; 16 } 17 int GetNumberOfK(vector<int> data ,int k) { 18 int index = getIndexbyDivision(data,k); 19 if(index == -1) return 0; 20 int num = 1; 21 for(int i = index - 1;i >= 0 && data[i] == k;i --) num++; 22 for(int j = index + 1;j < data.size() && data[j] == k;j ++) num++; 23 return num; 24 } 25 };
[剑指Offer] 37.数字在排序数组中出现的次数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。