题目描述
该类题目书中共有三题，以下为题目描述：
- 统计一个数字在排序数组中出现的次数。例如，输入排序树组 { 1, 2, 3, 3, 3, 3, 4, 5 } 和数字3， 由于3在这个数组中出现了4次，因此输出4.
Leetcode53-I：在排序数组中查找数字 I - 一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0 ~ n-1内。在范围0 ~ n-1内的n个数字中有且仅有一个数字不在该数组中，请找出这个数字。
Leetcode53-II：0～n-1中缺失的数字 - 假设一个单调递增的数组里的每个元素都是整数并且是唯一的。请编程实现一个函数，找出数组中任意一个数值等于其下标的元素。例如，在数组{ -3, -1, 1, 3, 5 }中，数字3和它的下标相等。
算法分析
因为是在排序数组中查找数字，所以优先考虑用二分查找完成（代码细节见注释）：
- 对于第一题，用二分查找分别求出该数字第一次出现的位置和最后一次出现的位置，相减即可得到答案。
- 对于第二题，用二分查找找到第一个值和下标不相等的元素即可。
- 对于第三题，用二分查找找到一个值与下标相等的元素即可。
复杂度分析
问题规模为数组的元素个数n
- 时间复杂度：O( l o g n logn logn)，二分查找的时间复杂度为logn。
- 空间复杂度：O( 1 1 1)。
Golang代码如下
func binarySearch53_1(nums []int, target int) int {
l, r := 0, len(nums) - 1
for l <= r {
mid := l + (r - l) / 2
if nums[mid] < target {
l = mid + 1
} else {
r = mid - 1
}
}
return l
}
func search(nums []int, target int) int {
if len(nums) == 0 {
return 0
}
left := binarySearch53_1(nums, target)
right := binarySearch53_1(nums, target+1) // 实际上返回的是比target大的第一个元素的索引（可能越界）
if left == right {
// 考虑数字不在数组中的特殊情况
if left >= len(nums) || nums[left] != target {
return 0
}
return 1
}
return right - left
}
func missingNumber(nums []int) (num int) {
l, r := 0, len(nums)-1
for l <= r {
mid := l + (r - l) / 2
if nums[mid] == mid {
l = mid + 1
} else {
if mid-1 >= 0 && nums[mid-1] == mid-1 {
num = mid
break
}
r = mid - 1
}
}
// 保证缺失的不是最后一个数字
if num == 0 && r == len(nums) - 1 {
return nums[r] + 1
}
return
}
func findNumberEqualToOffset(arr []int) (num int) {
l, r := 0, len(arr)-1
for l <= r {
mid := l + (r - l) / 2
if arr[mid] == mid {
num = mid
break
} else if arr[mid] < mid {
l = mid+1
} else {
r = mid-1
}
}
return
}