剑指offer 数字在排序数组中出现的次数

剑指offer 数字在排序数组中出现的次数

  • 题目描述

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

  • 题目解答

一看就是二分大法呀!

class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        int size = data.size();
		if (size == 0 || k<data[0] || k>data[size-1])
			return 0;
		int l = 0, r = size - 1;
		int count = 0;
		while (l <= r){
			int mid = l + (r - l) / 2;
			if (data[mid] == k){
				count++;
				for (int i = mid - 1; i >= 0 && data[i] == k; --i)
					count++;
				for (int j = mid + 1; j<size&&data[j] == k; ++j)
					count++;
				break;
			}
			else if (data[mid] > k){
				r = mid - 1;
			}
			else{
				l = mid + 1;
			}
		}
		return count;
    }
};
弹钢琴的猫 /
Published under (CC) BY-NC-SA in categories 算法  tagged with 剑指offer  Array