[leetcode]剑指 Offer 53 - I. 在排序数组中查找数字 I-爱代码爱编程
统计一个数字在排序数组中出现的次数。
示例 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
思路:
二分,同[leetcode]34.在排序数组中查找元素的第一个和最后一个位置,lower_bound与upper_bound的写法。
注意特殊情况的处理,特殊情况比较多。
AC代码:(C++)
class Solution {
public:
int upper_bound(vector<int>& nums, int target) {
//第一个大于target的元素
int left = 0, right = nums.size() - 1, mid;
while (left < right) {
mid = (right - left) / 2 + left;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int lower_bound(vector<int>& nums, int target) {
//第一个大于等于target的元素
int left = 0, right = nums.size() - 1, mid;
while (left < right) {
mid = (right - left) / 2 + left;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
int search(vector<int>& nums, int target) {
if (nums.size() == 0) return 0; //nums为空
if (nums.size() == 1) {
//nums中只有一个元素,判断这个元素是不是等于target
return nums[0] == target ? 1 : 0;
}
int left = lower_bound(nums, target);
int right = upper_bound(nums, target);
if (nums[left] != target) {
//此时nums中不存在target
return 0;
}
if (nums[right] == target) {
//target为nums中最大的元素,不存在第一个大于target的元素,于是减完要加一
return right - left + 1;
} else {
return right - left;
}
}
};