题解 | JZ53 数字在升序数组中出现的次数
这题对于C++来说是很好写的,因为C++已经帮我们实现好了在一个排好序中的数组中二分查找某个数。
lower_bound()函数对应着查找给数第一次出现的位置，upper_bound()函数对应着查找大于给定数出现第一次出现的位置。
因此，upper_bound()-lower_bound()的值，就是我们要查的数的出现次数。
而对于Python而言，我们需要实现这两个二分函数。
class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
int p1 = lower_bound(data.begin(), data.end(), k) - data.begin();
int p2 = upper_bound(data.begin(), data.end(), k) - data.begin();
return p2-p1;
}
};
#
# 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
#
#
# @param data int整型一维数组
# @param k int整型
# @return int整型
#
class Solution:
def GetNumberOfK(self , data: List[int], k: int) -> int:
# write code here
p1 = -1
p2 = -1
l = 0
r = len(data) - 1
while True:
if l > r:
break
mid = (l+r)//2
if data[mid] < k:
l = mid + 1
elif data[mid] > k:
r = mid - 1
else:
p1 = mid
r = mid-1
l = 0
r = len(data)-1
while True:
if l > r:
break
mid = (l+r)//2
if data[mid] > k:
r = mid - 1
elif data[mid] < k:
l = mid + 1
else:
p2 = mid
l = mid+1
if p2==-1: return 0
return p2-p1+1
查看3道真题和解析
