class Solution {
public:
int search(vector<int>& nums, int target) {
}
};
剑指 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] <= 109nums 是一个非递减数组-109 <= target <= 109
注意：本题与主站 34 题相同（仅返回值不同）：https://leetcode.cn/problems/find-first-and-last-position-of-element-in-sorted-array/
原站题解
golang 解法, 执行用时: 4 ms, 内存消耗: 3.9 MB, 提交时间: 2021-07-16 14:50:25
func search(nums []int, target int) int {
return sort.SearchInts(nums, target+1) - sort.SearchInts(nums, target)
}
golang 解法, 执行用时: 4 ms, 内存消耗: 3.9 MB, 提交时间: 2021-06-23 11:01:52
func search(nums []int, target int) int {
return sort.SearchInts(nums, target+1) - sort.SearchInts(nums, target)
}
golang 解法, 执行用时: 8 ms, 内存消耗: 3.9 MB, 提交时间: 2021-06-23 10:57:59
func search(nums []int, target int) int {
L := helper(nums, 0, len(nums)-1, target)
R := helper(nums, L, len(nums)-1, target+1)
return R-L
}
func helper(nums []int, low, high, target int) int {
for low <= high {
mid := (low+high)/2
if nums[mid] < target {
low = mid+1
} else {
high = mid-1
}
}
return low
}
golang 解法, 执行用时: 16 ms, 内存消耗: 3.9 MB, 提交时间: 2021-06-23 10:49:32
func search(nums []int, target int) int {
if len(nums) == 0 {
return 0
}
mid, ans := 0, 0
low, high := 0, len(nums)-1
for low <= high {
mid = (low+high)/2
if nums[mid] > target {
high = mid-1
} else if nums[mid] < target {
low = mid+1
} else {
break
}
}
if nums[mid] == target {
for i:=mid;i>=0;i-- {
if nums[i] < target {
break
}
ans++
}
for i:=mid;i<len(nums);i++ {
if nums[i] > target {
break
}
ans++
}
ans--
}
return ans
}