第 53 題：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù) （二分法典型問題）
傳送門：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
例如輸入排序數(shù)組
[1, 2, 3, 3, 3, 3, 4, 5]和數(shù)字 3 ，由于 3 在這個數(shù)組中出現(xiàn)了 4 次，因此輸出4。樣例：
輸入：
[1, 2, 3, 3, 3, 3, 4, 5], 3輸出：4
參考資料：《劍指 Offer》（第 2 版）第 53 題：數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
思路1：寫一個二分法，使用二分法找到大于等于 的第
個數(shù)的下標(biāo)，再使用二分法找到大于等于
的第
個數(shù)的下標(biāo)，二者之差即為所求。特別注意，這里是如何使用二分法的。
Python 代碼：
class Solution(object):
# 返回大于等于 target 的第 1 個數(shù)
def get_left(self, nums, target):
# [2,3,4,5,5,5,5,5,5,5]
# [1,1,1,1,1,1,1,1,1,2,3,4,5,5,5,5,5,5,5]
if nums[0] == target:
return 0
l = 1
r = len(nums)
while l < r:
mid = l + (r - l) // 2
if nums[mid] < target:
l = mid + 1
else:
assert nums[mid] >= target
# 不能排除 mid
r = mid
return l
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
return self.get_left(nums, k + 1) - self.get_left(nums, k)
嚴(yán)格按照二分法模板的話，代碼要這樣寫：
Python 代碼：
class Solution(object):
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
# 設(shè)置輔助函數(shù)，給一個 nums，一個 k，返回大于等于 k 的第一個數(shù)的索引
return self.__helper(nums, k + 1) - self.__helper(nums, k)
def __helper(self, nums, k):
"""
返回大于等于 k 的第一個數(shù)的索引
:param nums:
:param k:
:return:
"""
size = len(nums)
if size == 0:
return 0
l = 0
# 注意：這里一定要寫 size
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= k:
r = mid
else:
assert nums[mid] < k
# [1,2,3,4,5]
l = mid + 1
# 因?yàn)?k 有可能不存在，所以不一定符合要求，所以一定要單獨(dú)判斷一下
if nums[l] != k:
if nums[size - 1] < k:
return size
elif nums[0] > k:
return 0
return l
C++ 代碼：
class Solution {
public:
int getNumberOfK(vector<int>& nums , int k) {
if (nums.empty()) return 0;
return helper(nums, k + 1) - helper(nums, k);
}
int helper(vector<int>& nums, int k){
int l = 0, r = nums.size();
while (l < r){
int m = l + (r - l) / 2;
if (nums[m] < k) l = m + 1;
else r = m;
}
return l;
}
};
思路2：寫兩個二分法，一個數(shù)出現(xiàn)的次數(shù)，一個數(shù)最右邊的索引 - 一個數(shù)最左邊的索引 + 1。
# # 56、數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)
# 統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
#
# 例如輸入排序數(shù)組[1, 2, 3, 3, 3, 3, 4, 5]和數(shù)字3，由于3在這個數(shù)組中出現(xiàn)了4次，因此輸出4。
class Solution(object):
def getNumberOfK(self, nums, k):
"""
:type nums: list[int]
:type k: int
:rtype: int
"""
size = len(nums)
if size == 0:
return 0
# 設(shè)置輔助函數(shù)，給一個 nums，一個 k，返回大于等于 k 的第一個數(shù)的索引
k_right = self.__get_right_k(nums, k)
k_left = self.__get_left_k(nums, k)
if k_right == -1 or k_left == -1:
return 0
return k_right - k_left + 1
def __get_right_k(self, nums, k):
# 找到最右邊的 index ，使得 nums[index] = k
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l + 1) // 2
if nums[mid] <= k:
# [1,2,5,5,5,7]
l = mid
elif nums[mid] > k:
r = mid - 1
if nums[l] != k:
return -1
return l
def __get_left_k(self, nums, k):
# 找到最左邊的 index ，使得 nums[index] = k
size = len(nums)
if size == 0:
return -1
l = 0
r = size - 1
while l < r:
mid = l + (r - l) // 2
if nums[mid] >= k:
r = mid
else:
assert nums[mid] < k
l = mid + 1
if nums[l] != k:
return -1
return l
if __name__ == '__main__':
nums = [2, 3, 4, 5, 5, 5, 5, 5, 5, 5, 6, 7, 8, 9, 10]
k = 5
solution = Solution()
# result = solution.get_left(nums, 5, )
# print(result)
result = solution.getNumberOfK(nums, k)
print(result)
