手写二分
class Solution(object):
def getRight(self, q, l, r, k):
while l < r:
mid = l + r + 1 >> 1
if q[mid] <= k: l = mid
else: r = mid - 1
return l
def getLeft(self, q, l, r, k):
while l < r:
mid = l + r >> 1
if q[mid] >= k: r = mid
else: l = mid + 1
return l
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
n = len(nums)
if n == 0: return 0
left = self.getLeft(nums, 0, n - 1, k)
if nums[left] != k:
return 0
right = self.getRight(nums, 0, n - 1, k)
return right - left + 1
内置二分
class Solution(object):
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
from bisect import bisect_left, bisect_right
return bisect_right(nums, k) - bisect_left(nums, k)