剑指 Offer 53 – I. 在排序数组中查找
本问题对应的 leetcode 原文链接：剑指 Offer 53 – I. 在排序数组中查找
对应打卡问题：【二叉树专题】剑指 Offer 53 – 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] <= 109nums是一个非递减数组-109 <= target <= 109
解题思路
视频讲解直达： 本题视频讲解
代码实现
class Solution {
public int search(int[] nums, int target) {
//常见题型：
// 1.寻找第一个大于等于 target 的数 2.寻找第一个等于 target 的数
// 3.寻找最后一个大于等于 target 的数 4.寻找最后一个等于 target 的数
//PS：其实这里是不需要写两个查找函数的，可以把代码优化放在同一个方法里滴
int left = search2(nums, target);
int right = search4(nums, target);
if(left < 0 || right < 0) return 0;
return right - left + 1;
}
//2.寻找第一个等于 target 的数的下标
int search2(int[] nums, int target){
if(nums == null || nums.length <= 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
// 向下取整
int mid = (right - left) / 2 + left;
if(nums[mid] >= target){
right = mid;
}else{
left = mid + 1;
}
}
// 判断该数是否存在
if(nums[left] != target) return -1;
return left;
}
//4.寻找最后一个等于 target 的数下标
int search4(int[] nums, int target){
if(nums == null || nums.length <= 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
//向上取整
int mid = (right - left + 1) / 2 + left;
if(nums[mid] <= target){
left = mid;
}else{
right = mid - 1;
}
}
// 判断该数是否存在
if(nums[left] != target) return -1;
return left;
}
}
时间复杂度：log(n)
额外空间复杂度：O(1)