title: 每日一练(24):在排序数组中查找数字
categories:[剑指offer]
tags:[每日一练]
date: 2022/02/23
每日一练(24):在排序数组中查找数字
统计一个数字在排序数组中出现的次数。
示例 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)
链接:https://leetcode-cn.com/problems/zai-pai-xu-shu-zu-zhong-cha-zhao-shu-zi-lcof
方法一:STL(一行搞定)
count函数可以用来统计字符串中某个字符的个数
使用方法是count(ivec.begin() , ivec.end() , searchValue),其中begin指的是起始地址,end指的是结束地址,第三个参数指的是需要查找的字符。
int search(vector<int>& nums, int target) {
return count(nums.begin(),nums.end(),target);
}
方法二:暴力解法
直接for循环遍历查找目标并计数
int search(vector<int>& nums, int target) {
if (nums.size() == 0) {
return 0;
}
if (nums.size() == 1) {
if (nums[0] == target) {
return 1;
} else {
return 0;
}
}
int count = 0;
for (int i = 0; i < nums.size(); i++) {
if (nums[i] == target) {
count++; //循环计数
}
}
return count;
}
方法三:二分查找
二分模板:
模板1
当我们将区间[l, r]划分成[l, mid]和[mid + 1, r]时,其更新操作是r = mid或者l = mid + 1,计算mid时不需要加1,即mid = (l + r)/2。
int bsearch_1(int l, int r)
{
while (l < r)
{
int mid = (l + r)/2;
if (check(mid)) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
模板2
当我们将区间[l, r]划分成[l, mid - 1]和[mid, r]时,其更新操作是r = mid - 1或者l = mid,此时为了防止死循环,计算mid时需要加1,即mid = ( l + r + 1 ) /2。
int bsearch_2(int l, int r)
{
while (l < r)
{
int mid = ( l + r + 1 ) /2;
if (check(mid)) {
l = mid;
} else {
r = mid - 1;
}
}
return l;
}
lowerBound(target)
upper(target+1)
时间复杂度分析: 两次二分查找的时间复杂度为 O(logn)。
空间复杂度分析: 没有使用额外的数组,因此空间复杂度为O(1)。
int lowerBound(vector<int>& nums, int target) {
int l, r;
l = 0;
r = nums.size();
while (l < r) {
int mid = (l + r) >> 1;
if (target <= nums[mid]) {
r = mid;
} else {
l = mid + 1;
}
}
return l;
}
int search(vector<int>& nums, int target) {
int lower = lowerBound(nums, target);
int upper = lowerBound(nums, target + 1);
return (upper - lower);
}