题目
统计一个数字在排序数组中出现的次数。
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8 输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6 输出: 0
解题
方法一：暴力
class Solution { public: int search(vector<int>& nums, int target) { int res=0; for(int num:nums){ if(num==target) res++; } return res; } };
方法二：二分查找
对于left=mid+1，right=mid-1， if(nums[mid]<=target)这样子的写法
比如 nums = [5,7,7,8,8,10]，要查找target=8
left会到10,right会到最右边那个8，然后中止循环。
因此比如 nums = [5,7,7,8,8,10]，要查找target=8，利用helper(nums,target)-helper(nums,target-1)，
第一个返回值为5,第二个返回值为3
class Solution { public: int helper(vector<int>& nums,int target){ int left=0,right=nums.size()-1; while(left<=right){ int mid=(left+right)/2; if(nums[mid]<=target) left=mid+1; else right=mid-1; } return left; } int search(vector<int>& nums, int target) { return helper(nums,target)-helper(nums,target-1); } };
