首页 > 代码库 > 面试题38_数字在排序数组中出现的次数
面试题38_数字在排序数组中出现的次数
题目描写叙述
统计一个数字在排序数组中出现的次数。
解题思路
数组是排序的,所以反复出现的数字是相邻排列的。
用二分查找算法,找到第一次出现的位置。和 最后一次出现的位置。
推断第一次出现的位置条件为:当前数字的前一个是否与之相等。若是则继续查找,否则该位置就是第一次出现的位置。
推断最后一次出现的位置条件为:当前数字的后一个是否与之相等,若是则继续查找,否则该位置就是最后一次出现的位置。
出现的次数= last - first +1
时间复杂度:O(logn)
实现代码
class Solution { public: int GetNumberOfK(vector<int> data ,int k) { int result=0; if(data.empty()) return 0; int start = 0; int end = data.size()-1; int first = getFirstK(data,k,start,end); int last = getLastK(data,k,start,end); if(first >-1 && last >-1) result = last - first+1; return result; } int getFirstK(vector<int> data, int k, int start, int end) { if(start > end) return -1; int midIndex = (start + end)/2; int midData = http://www.mamicode.com/data[midIndex];>
面试题38_数字在排序数组中出现的次数
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。