题目内容
统计一个数字在排序数组中出现的次数。
示例
示例 1:
输入: nums = [5,7,7,8,8,10], target = 8
输出: 2
示例 2:
输入: nums = [5,7,7,8,8,10], target = 6
输出: 0
提示:
0 <= nums.length <= 105
-109 <= nums[i] <= 109
nums 是一个非递减数组
-109 <= target <= 109
思路
最初只想到了顺序查找
看评论题解发现大家都用的二分。启发:有序的时候要想着用二分。
这个代码很妙,把cnt加入,便于进行查找计数。
class Solution {
int cnt = 0; // 计数器count
public int search(int[] nums, int target) {
// 初始化low = 0, high = nums.length - 1
helper(nums, target, 0, nums.length - 1);
return cnt;
}
// 根据算法设计分3种情况
public void helper(int[] nums, int target, int low, int high) {
if (low <= high) {
int mid = (high - low) / 2 + low;
if (nums[mid] == target) {
cnt++; // 计数一次
helper(nums, target, low, mid - 1);
helper(nums, target, mid + 1, high);
} else if (nums[mid] > target) {
helper(nums, target, low, mid - 1);
} else {
helper(nums, target, mid + 1, high);
}
}
}
}
标签:target,helper,nums,--,Offer,二分法,int,查找,low
From: https://www.cnblogs.com/DXD-blog/p/16977274.html