原题
给出一个目标数字和一个升序整数数组，返回目标数字在数组中出现的次数。
- 给出 [1, 3, 3, 4, 5] 并且 target = 3, 返回 2.
- 给出 [2, 2, 3, 4, 6] 并且 target = 4, 返回 1
- 给出 [1, 2, 3, 4, 5] 并且 target = 6, 返回 0
解题思路
- 二分法， 分两步：找到第一个出现的位置， 找到最后一个出现的位置。就可以计算出出现频率
完整代码
class Solution:
# @param {int[]} A an integer array sorted in ascending order
# @param {int} target an integer
# @return {int} an integer
def totalOccurrence(self, A, target):
# Write your code here
if not A:
return 0
start, end = 0, len(A) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] <= target:
start = mid
else:
end = mid
if A[end] == target:
right = end
elif A[start] == target:
right = start
else:
return 0
start, end = 0, len(A) - 1
while start + 1 < end:
mid = start + (end - start) / 2
if A[mid] >= target:
end = mid
else:
start = mid
if A[start] == target:
left = start
elif A[end] == target:
left = end
else:
return 0
return right - left + 1
