题目链接

LeetCode

题目描述

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

  1. 输入: nums = [5,7,7,8,8,10], target = 8
  2. 输出: 2
  4. 输入: nums = [5,7,7,8,8,10], target = 6
  5. 输出: 0

解题思路

二分查找

  1. bin_search(int A[],int n,int key){
  2.     int low,high,mid;
  3.     low = 0;
  4.     high = n-1;
  5.     while(low<=high)
  6.     {
  7.         mid =(low + high)/2;
  8.         if(A[mid]==key)return mid;
  9.         if(A[mid]<key){
  10.             low =mid + 1;
  11.         }
  12.         if(A[mid]>key){
  13.             high= mid - 1;
  14.         }
  15.     }
  16.     return -1;
  17. }
  1. class Solution {
  2. public:
  3.     int search(vector<int>& nums, int target) {
  4.         if(nums.empty())
  5.             return 0;
  6.         int len = nums.size()-1;
  7.         if(nums[0]>target||nums[len]<target)
  8.             return 0;
  9.         return firstIndex(nums,target+1,len) - firstIndex(nums,target,len);
  10.     }
  11.     int firstIndex(vector<int>& nums, int target, int len){
  12.         int left = 0,right = len;
  13.         while(left<=right){
  14.             int mid = left + (right-left)/2;
  15.             if(nums[mid] >= target){
  16.                 right = right - 1; 
  17.             }else{
  18.                 left = mid + 1;
  19.             }
  20.         }
  21.         return left;
  22.     }
  23. };
  • 时间复杂度：O(logN)
  • 空间复杂度：**O(1)**