剑指 Offer 53 – I. 在排序数组中查找
本问题对应的 leetcode 原文链接：剑指 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)
Python
class Solution(object):
def search(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: int
"""
# 寻找第一个大于等于 target 的数的下标
def search1(nums, target):
if not nums:
return -1
left, right = 0, len(nums) - 1
while left < right:
mid = (right - left) // 2 + left
if nums[mid] < target:
left = mid + 1
else:
right = mid
return left
# 寻找最后一个大于等于 target 的数的下标
def search2(nums, target):
if not nums:
return -1
left, right = 0, len(nums) - 1
while left < right:
mid = (right - left + 1) // 2 + left
if nums[mid] > target:
right = mid - 1
else:
left = mid
return left
left = search1(nums, target)
right = search2(nums, target)
if left == -1 or right == -1 or nums[left] != target or nums[right] != target:
return 0
return right - left + 1
C++
class Solution {
public:
int search(vector<int>& nums, int target) {
// 寻找第一个大于等于 target 的数的下标
auto search1 = [&](vector<int>& nums, int target) -> int {
if (nums.empty()) {
return -1;
}
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
};
// 寻找最后一个大于等于 target 的数的下标
auto search2 = [&](vector<int>& nums, int target) -> int {
if (nums.empty()) {
return -1;
}
int left = 0, right = nums.size() - 1;
while (left < right) {
int mid = left + (right - left + 1) / 2;
if (nums[mid] > target) {
right = mid - 1;
} else {
left = mid;
}
}
return left;
};
int left = search1(nums, target);
int right = search2(nums, target);
if (left == -1 || right == -1 || nums[left] != target || nums[right] != target) {
return 0;
}
return right - left + 1;
}
};
Go
func search(nums []int, target int) int {
// 寻找第一个大于等于 target 的数的下标
search1 := func(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left, right := 0, len(nums) - 1
for left < right {
mid := left + (right - left) / 2
if nums[mid] < target {
left = mid + 1
} else {
right = mid
}
}
return left
}
// 寻找最后一个大于等于 target 的数的下标
search2 := func(nums []int, target int) int {
if len(nums) == 0 {
return -1
}
left, right := 0, len(nums) - 1
for left < right {
mid := left + (right - left + 1) / 2
if nums[mid] > target {
right = mid - 1
} else {
left = mid
}
}
return left
}
left := search1(nums, target)
right := search2(nums, target)
if left == -1 || right == -1 || nums[left] != target || nums[right] != target {
return 0
}
return right - left + 1
}
JS
/**
* @param {number[]} nums
* @param {number} target
* @return {number}
*/
var search = function(nums, target) {
//常见题型：
// 1.寻找第一个大于等于 target 的数 2.寻找第一个等于 target 的数
// 3.寻找最后一个大于等于 target 的数 4.寻找最后一个等于 target 的数
//PS：其实这里是不需要写两个查找函数的，可以把代码优化放在同一个方法里滴
let left = search2(nums, target);
let right = search4(nums, target);
if (left < 0 || right < 0) return 0;
return right - left + 1;
};
//2.寻找第一个等于 target 的数的下标
function search2(nums, target) {
if (nums == null || nums.length <= 0) {
return -1;
}
let left = 0,
right = nums.length - 1;
while (left < right) {
// 向下取整
let mid = Math.floor((right - left) / 2 + left);
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
// 判断该数是否存在
if (nums[left] != target) return -1;
return left;
}
//4.寻找最后一个等于 target 的数下标
function search4(nums, target) {
if (nums == null || nums.length <= 0) {
return -1;
}
let left = 0,
right = nums.length - 1;
while (left < right) {
//向上取整
let mid = Math.ceil((right - left + 1) / 2 + left);
if (nums[mid] <= target) {
left = mid;
} else {
right = mid - 1;
}
}
// 判断该数是否存在
if (nums[left] != target) return -1;
return left;
}